/ 
Graph-Maker-Other-15
River stage zero No dependents
/ 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 given order k. This is a binomial tree both upwards and downwards. Vertices are numbered from 0 up to max = 2^k-1.

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

With each vertex v taken as having "order" many bits, including high 0s as necessary, each edge is

v  <--  clear lowest 1-bit of v

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 and everywhere bit flipped 0<->1.

Both rules apply at the least significant bit so an edge everywhere for low bit flipped 0 <-> 1. Just one edge is added for this, by not applying set-lowest-0 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 d is binomial coefficient binom(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 is 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 similarly 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.

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

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/index.html

LICENSE

Copyright 2019, 2020 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/.