13 problems

The Small Set Expansion hypothesis
arXiv@arxiv
Small Set Expansion hypothesis. For any $\varepsilon>0$ , there is a constant $\delta\in(0,1)$ such that no polynomial-time algorithm can distinguish between the case…
Conjectureopencomputational-complexity graph-expansion small-set-expansion
1
Polynomial inverse-dimension edge-expansion bound for 0/1-polytopes
arXiv@arxiv
Let $P$ be a $d$ -dimensional 0/1-polytope, meaning the convex hull of a set of points whose coordinates belong to $\{0,1\}$ . Its graph has the vertices of $P$ as nodes and the edge…
Conjectureopen0-1-polytopes graph-expansion random-walks
0
Benjamini–Lyons–Schramm positive-speed conjecture for anchored-expansion graphs
arXiv@arxiv
Let $G$ be an unweighted graph with bounded degree and anchored expansion, and consider simple random walk on $G$ . Benjamini–Lyons–Schramm positive-speed conjecture. The random wal…
Conjectureopengraph-expansion probability random-walks
0
Subdivision conjecture for percolated vertex expanders
arXiv@arxiv
Fix $d\in\mathbb{N}$ and let $H$ be a graph of maximum degree $3$ . Let $k\in\mathbb{N}$ , and let $G$ be an $(=\hspace{-0.2em}k,d)$ -vertex expander, meaning that every set…
Conjectureopengraph-expansion graph-subdivisions random-graphs
0
Collares–Diskin–Erde–Krivelevich long-cycle conjecture for percolated vertex expanders
arXiv@arxiv
Let $G$ be a graph, and let $G_p$ be obtained by retaining each edge independently with probability $p$ . Suppose that $G$ satisfies the assumptions of the cited path theorem: for s…
Conjectureopengraph-expansion long-cycles random-graphs
0
Quantitative Benjamini conjecture for heat-kernel expansion
arXiv@arxiv
Let $\mathcal{G}$ be an infinite, irreducible, bounded-degree graph, let $\nu_{L,o}$ denote the $L$ -step heat-kernel measure rooted at $o$ , and let $\partial A$ be the boundary of…
Conjecturerefutedgraph-expansion random-walks thermalization
1
Krylov-graph shattering conjecture for exponentially fragmented dynamics
arXiv@arxiv
Let ${\sf Dyn}$ be a constrained dynamics and let $\mathcal{G}_{\mathcal{K}}$ be its Krylov graph. Suppose that ${\sf Dyn}$ is exponentially fragmented. Krylov-graph shattering con…
Conjecturerefutedgraph-expansion hilbert-space-fragmentation thermalization
0
Universality of majority bootstrap percolation in expanding approximately regular graphs
arXiv@arxiv
Universality conjecture. The behaviour of majority bootstrap percolation is universal across all such graphs.
Conjectureopenbootstrap-percolation graph-expansion random-graphs
0
Polynomial edge-expansion conjecture for 0/1 polytopes
arXiv@arxiv
Weaker Mihail–Vazirani conjecture. There is a polynomial function $f$ such that the edge expansion of $G(P)$ is greater than $\frac{1}{f(d)}$ .
Conjectureopengraph-expansion polytopes random-walks
1
Aldous–Fill hitting-time conjecture for isoperimetic regular graphs
arXiv@arxiv
Let $G=(V,E)$ be a bounded-degree, $d$ -regular graph with $n=|V|$ vertices. For a subset $A\subseteq V$ , write $A^c=V\setminus A$ and let $|E(A,A^c)|$ denote the number of edges cr…
Conjectureopengraph-expansion hitting-times random-walks
0
Goldreich–Ron conjecture on testing graph expansion
arXiv@arxiv
Goldreich and Ron considered testing expansion in bounded-degree graphs by selecting a random node and testing whether random walks from it approach the uniform distribution on the…
Conjectureopengraph-expansion markov-chains property-testing
0
Subgraph-closed classes with strongly sublinear separators have subexponential expansion
arXiv@arxiv
Let ${\cal G}$ be a subgraph-closed class of graphs. Suppose that ${\cal G}$ has strongly sublinear separators. Subexponential expansion conjecture. The expansion of ${\cal G}$ is…
Conjectureopengraph-classes graph-expansion graph-separators
0
Depth-bound conjecture for vertex-transitive graphs
arXiv@arxiv
Let $G$ be a connected vertex-transitive graph, let $A\subseteq V(G)$ be finite with $0<|A|\leq \tfrac12|V(G)|$ , let $\partial A$ denote the vertex boundary of $A$ , and let…
Conjectureopengraph-expansion vertex-transitive-graphs
0