The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ Graph::Maker::BinomialBoth

NAME

Graph::Maker::BinomialBoth - create binomial both graph

SYNOPSIS

 use Graph::Maker::BinomialBoth;
 $graph = Graph::Maker->new ('binomial_both', order => 3,
                             direction_type => 'bigger');

DESCRIPTION

Graph::Maker::BinomialBoth creates a Graph.pm graph of a "binomial both" of order k. This is a binomial tree both upwards and downwards. Vertices are numbered from 0 up to max = 2^k-1 where k is the "order".

    0----
    | \  \
    1  2  4            order => 3
     \ |  | \          vertices 0 to 7
       3  5  6
        \  \ |
         ----7

Each vertex v is taken as k many bits, including high 0s as necessary. Each edge is

    from            to
    ----   -----------------------
     v     clear lowest 1-bit of v       \ edges
     v     set lowest 0-bit of v         /

Clear-lowest-1 is the parent of v in the binomial tree (Graph::Maker::BinomialTree). Set-lowest-0 is the same applied towards the maximum vertex 2^k-1, as if that was the root by everywhere bit flip 0<->1.

Both rules apply at the least significant bit, which is the low bit flipped 0 <-> 1. Just one edge is added for this, by not applying the set-lowest-0 rule at the low bit. Consequently there are 2^k-1 edges of clear-lowest-1 and 2^(k-1)-1 edges of set-lowest-0 for total

    num_edges(k) = / 0                  if k = 0
                   \ 3 * 2^(k-1) - 2    if k >= 1
                 = 0, 1, 4, 10, 22, 46, 94, 190, ...  (A296953)

Each edge changes just one bit so binomial both is a sub-graph of hypercube k (Graph::Maker::Hypercube).

A top-down definition is to make order k from two copies of k-1. The max of the first connects down to the max of the second, and the min of the first connects down to the min of the second.

          min
    first |.| \
          |.|   min
          max   |.| second
              \ |.|
                max

Direction Type

The default is a directed graph with edges both ways between vertices (like most Graph::Maker directed graphs). This is parameter direction_type => 'both'.

Optional direction_type => 'bigger' gives edges directed to the bigger vertex number, so from smaller to bigger. The result is a graded lattice (the algebra type of lattice, partially ordered set) with edges its cover relations. (The name "binomial lattice" is normally given to the grid type lattice formed by random share price movements, so here "binomial both" instead.)

The lattice is graded by d = number of 1-bits in the vertex number, which is the binomial tree depth. Like the binomial tree, the number of vertices at depth d is binomial coefficient binomial(k,d).

Option direction_type => 'smaller' gives edges directed to the smaller vertex number, so from bigger to smaller. This is the same as $graph->transpose() reversing edges.

Coordinates

There's a secret undocumented coordinates option the same as the binomial tree "Coordinates" in Graph::Maker::BinomialTree. Don't rely on this yet as it might change or be removed.

FUNCTIONS

$graph = Graph::Maker->new('binomial_both', key => value, ...)

The key/value parameters are

    order          =>  integer >=0
    direction_type =>  string, "both"    (default)
                               "bigger"
                               "smaller"
    graph_maker    =>  subr(key=>value) constructor,
                         default Graph->new

Other parameters are passed to the constructor, either graph_maker or Graph->new().

If the graph is directed (the default) then edges are added as described in "Direction Type". Option undirected => 1 creates an undirected graph and for it there is always a single edge between relevant vertices.

FORMULAS

Successors

As a lattice of direction "bigger", the full set of eventually reachable all_successors() of a vertex v is formed by setting any combination of its low 0-bits to 1-bits, and setting all those low 0s to 1s plus successively low to high each other 0 to 1. For example

    v =  101101100  \
         101101101  |   4 combinations of low 0s
         101101110  |
         101101111  /
         101111111  \   then all low 0s to 1s and
         111111111  /   successively set each other 0

The all-of-low-0s is the max of a sub-lattice containing v. The successive other 0s are the path (sole path) from that sub-lattice max to the global max. If v has no low 0s then just this path to the global max is all its reachable successors.

Maximal Chains

A maximal chain in a lattice is a path from global min to global max. In the graph here, this is the number of paths from v=0 to v=2^k-1 in direction type "bigger".

    num_max_chains(k) = / 1           if k=0
                        \ 2^(k-1)     if k>=1
                     = 1, 1, 2, 4, 8, 16, ...   (A011782)

In the top-down definition above, a path can go through the first half or second half, and then the same recursively in quarters etc until k=1 is 2 vertices and just one path.

Intervals

An interval in a lattice is a pair of vertices u,v which are comparable. In the graph with direction type "bigger", this means one vertex is reachable from the other by some directed path. u=v is an interval too.

    num_intervals(k) = k*2^k + 1         Cullen numbers
                     = 1, 3, 9, 25, 65, 161, 385, ...   (A002064)

In the top-down definition, order k formed from two k-1 gives new intervals from first half min to each second half vertex, and from each of the other first half vertices to the second half max. So the following recurrence, and from which the Cullen numbers,

    num_intervals(k) = 2*num_intervals(k-1) + 2^(k-1) + 2^(k-1) - 1

Complementary Pairs

A complementary pair in a lattice is two vertices u,v where their meet and join are the global min and global max. In the graph with direction type "bigger", this means $u->all_predecessors() and $v->all_predecessors() have only the global minimum (0) in common, and also all_successors() only the global maximum in common (2^k-1).

    num_complementary(k) = /  1                       if k=0
                           \  (2^(k-1) - 1)^2 + 1     if k>=1
                         = 0, 1, 2, 10, 50, 226, ...  (2*A092440)

This count follows from the top-down definition. Pairs within a half have the half min and max in common, only one of those is the global min/max, so no complementary pairs. The first half min has all of the second half as descendants, so only first half min as global smallest and second max as global biggest are a pair. Then the other 2^(k-1)-1 vertices of the first half are complementary to the 2^(k-1)-1 vertices of the second half except the second max which is the global maximum. For k=0, the single vertex is a complementary pair 0,0.

Wiener Index

The top-down definition means the Wiener index of order k+1 is twice k plus paths from the first k to the second k. Those paths go by the top edge or the bottom edge between the halves, whichever is the shorter way. So a sum over depth u in the first, depth v in the second, with respective numbers of vertices at those depths,

               k   k
    Wnew(k) = sum sum  binomial(k,u) * binomial(k,v)
              u=0 v=0    * min(u+v+1, (k-u)+(k-v)+1)

            = 1, 6, 36, 196, 1000, 4884, 23128, ...

    W(k+1) = 2*W(k) + Wnew(k)           Wiener index
      starting W(k)=0

    W(k) = 0, 1, 8, 52, 300, 1600, 8084, 39296, ...

For comparison, the Wiener index of the binomial tree is this sum but always u+v+1 instead of min().

A bottom-up approach in the binomial both is to consider each vertex duplicating to a new vertex below, like the binomial tree bottom-up definition. An existing path between vertices in k becomes 4 paths in k+1.

    top  ......        A  to B  distance L
        |      |       A  to B' distance L+1
        A      B       A' to B  distance L+1
        |      |       A' to B' distance L+2 top way
    new A'     B'                       ----
                                        4L+4

    or if A to B path in k are same distance by top or bottom
    then A' to B' can go the bottom way for distance L and total
                   L + L+1 + L+1 + L  = 4L+2

Each same-distance path in k is between opposite vertices. For example, the following is two j=4 blocks with binomial number of vertices at depths a to e.

    a 1----1 e'
      |    |         paths between
    b 4    4 d'      two j=4 blocks
      |    |
    c 6    6 c'      a to a' distance L=5 either way around
      |    |         b to b' likewise, etc
    d 4    4 b'
      |    |
    e 1----1 a'

The number of vertices at a depth and its opposite is the same binomial(j,depth) each. So with 2^(k-j) sub-block pairs of each sub-order j, each depth i, and binomial*binomial vertices each side, and each of these paths 2 shorter than the other paths (4L+2 rather than 4L+4),

                                       k           j
    W(k+1) = 4*W(k) + 4*Wpairs(k) - 2*sum 2^(k-j) sum binomial(j,i)^2
                                      j=0         i=0

    Wpairs(k) = binomial(num_vertices(k), 2)
              = 2^k * (2^k-1) / 2
              = 0, 1, 6, 28, 120, 496, 2016, ...      (A006516)

Sum(binomial^2) is the central binomial coefficient binomial(2*j,j). Its generating function is 1/sqrt(1 - 4*x). Working through that with some usual recurrence or generating function manipulations for a convolution to multiply 2^(k-j) and accumulate, gives a D-finite recurrence (coefficients are rational functions of k),

            2    /     ( 14*k- 34) * W(k-1)   \
    W(k) = --- * |   - ( 72*k-204) * W(k-2)   |     for k>=4 
           k-2   |   + (160*k-512) * W(k-3)   |
                 \   - (128*k-448) * W(k-4)   /

Or with a power of 4, and a generating function in that style,

            2    /     (3*k-5) * W(k-1)   \
    W(k) = --- * |   - (4*k-6) * W(k-2)   |     for k>=3
           k-2   \   + (  k-3) * 4^(k-2)  /
                 
              x      /     1             2*x      \
    gW(x) = ----- * |  ---------  - -------------  |
            1-2*x    \ (1-4*x)^2    (1-4*x)^(3/2) /

In the generating function, the last term 2*x /(1-4*x)^(3/2) is the Apery numbers k*binomial(2*k,k) (OEIS A005430). So without the 1/(1-2*x) convolution, this gives the Wnew paths as

    Wnew(k) = (k+1)*4^k - k*binomial(2*k,k)

Roughly speaking, this would be 2^k*2^k new paths with average length k+1 but less the binomial term.

HOUSE OF GRAPHS

House of Graphs entries for the graphs here include

    1310    order=0, single vertex
    19655   order=1, path-2
    674     order=2, 4-cycle
    35455   order=3, cross-connected 4-cycles
    35447   order=4
    35449   order=5
    35451   order=6
    35453   order=7

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to the graphs here include

    A296953   num edges
    A011782   num intervals
    A011782   num maximal chains
    A002064   1/2 * num complementary pairs, k>=2

SEE ALSO

Graph::Maker, Graph::Maker::BinomialTree, Graph::Maker::Hypercube

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2019, 2020, 2021, 2022 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.