A372705 -id:A372705 - cp's OEIS frontend

A373035 Number of edge subsets E of the n-dimensional hypercube graph such that E contains a path between two given antipodal nodes.

1, 1, 7, 2160, 3127853061

Offset: 0

Pontus von Brömssen, May 20 2024

a(n)/A061301(n) is the probability that two given antipodal nodes of the n-dimensional hypercube graph are still connected after each edge has been independently deleted with probability 1/2.

Main diagonal of A373034.

Cf. A061301, A372705, A373037.

A373034 Triangle read by rows: T(n,k) is the number of edge subsets E of the n-dimensional hypercube graph such that E contains a path between two given nodes at Hamming distance k, 0 <= k <= n.

Original entry on oeis.org

1, 2, 1, 16, 9, 7, 4096, 2703, 2334, 2160, 4294967296, 3425712321, 3245350248, 3170502909, 3127853061

Offset: 0

Pontus von Brömssen, May 20 2024

T(n,k)/A061301(n) is the probability that two given nodes at Hamming distance k in the n-dimensional hypercube graph are still connected after each edge has been independently deleted with probability 1/2.

The bunkbed conjecture (the version where all edges, including the posts, have the same probability 1/2 of being retained) holds for the n-dimensional hypercube graph if and only if the (n+1)-st row is nonincreasing.

			Triangle begins:
           1;
           2,          1;
          16,          9,          7;
        4096,       2703,       2334,       2160;
  4294967296, 3425712321, 3245350248, 3170502909, 3127853061;
  ...

Wikipedia, Bunkbed conjecture.

Cf. A061301 (first column), A372705, A373035 (main diagonal).

A377762 Number of edge cuts in the hypercube graph Q_n.

Original entry on oeis.org

0, 1, 11, 3013, 3055641151

Offset: 0

Eric W. Weisstein, Nov 06 2024

Eric Weisstein's World of Mathematics, Edge Cut.
Eric Weisstein's World of Mathematics, Hypercube Graph.

Cf. A061301, A372705.

a(n) = A061301(n)-A372705(n). - Pontus von Brömssen, Nov 06 2024

a(4) from Pontus von Brömssen, Nov 06 2024

cp's OEIS Frontend

A373035 Number of edge subsets E of the n-dimensional hypercube graph such that E contains a path between two given antipodal nodes.

Views

Author

Keywords

Comments

Crossrefs

A373034 Triangle read by rows: T(n,k) is the number of edge subsets E of the n-dimensional hypercube graph such that E contains a path between two given nodes at Hamming distance k, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A377762 Number of edge cuts in the hypercube graph Q_n.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions