Bunkbed conjecture for complete bipartite graphs and related classes of graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917965144784896 |
|---|---|
| author | Richthammer, Thomas |
| author_facet | Richthammer, Thomas |
| contents | Let $G = (V,E)$ be a simple finite graph. The corresponding bunkbed graph $G^\pm$ consists of two copies $G^+ = (V^+,E^+),G^- = (V^-,E^-)$ of $G$ and additional edges connecting any two vertices $v_+ \in V_+,v_- \in V_-$ that are the copies of a vertex $v \in V$. The bunkbed conjecture states that for independent bond percolation on $G^\pm$, for all $v,w \in V$, it is more likely for $v_-,w_-$ to be connected than for $v_-,w_+$ to be connected. While this seems very plausible, so far surprisingly little is known rigorously. Recently the conjecture has been proved for complete graphs. Here we give a proof for complete bipartite graphs, complete graphs minus the edges of a complete subgraph, and symmetric complete $k$-partite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_12931 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Bunkbed conjecture for complete bipartite graphs and related classes of graphs Richthammer, Thomas Probability Combinatorics 60K35, 05C80, 82B43, 05A20 Let $G = (V,E)$ be a simple finite graph. The corresponding bunkbed graph $G^\pm$ consists of two copies $G^+ = (V^+,E^+),G^- = (V^-,E^-)$ of $G$ and additional edges connecting any two vertices $v_+ \in V_+,v_- \in V_-$ that are the copies of a vertex $v \in V$. The bunkbed conjecture states that for independent bond percolation on $G^\pm$, for all $v,w \in V$, it is more likely for $v_-,w_-$ to be connected than for $v_-,w_+$ to be connected. While this seems very plausible, so far surprisingly little is known rigorously. Recently the conjecture has been proved for complete graphs. Here we give a proof for complete bipartite graphs, complete graphs minus the edges of a complete subgraph, and symmetric complete $k$-partite graphs. |
| title | Bunkbed conjecture for complete bipartite graphs and related classes of graphs |
| topic | Probability Combinatorics 60K35, 05C80, 82B43, 05A20 |
| url | https://arxiv.org/abs/2204.12931 |