In 1999, two papers of Benjamini, Lyons, Peres, and Schramm showed that for Bernoulli percolation on unimodular nonamenable quasi-transitive graphs, there are no infinite clusters at criticality. Using the theory of countable Borel equivalence relations and Gaboriau's cluster graphing construction, we give a short proof of this result. We also point out other uses of the cluster graphing construction in the literature, for instance in showing nonuniqueness at $p_u$ in arXiv:1509.00247 [math.GR]. The purpose of this short note is to make folklore proofs known to experts more accessible to the wider community of probabilists and measured group theorists.
We introduce and study a finite simple graph of algebraic origin: the Vieta graph on the solution set over $\mathbb{F}_p$ to a symmetric, multivariate equation which is quadratic in each variable. This construction is a broad generalization of the Markoff graph over $\mathbb{F}_p$, extensively studied in the recent literature. We give a systematic approach, partly based on quadratic character sums, to the following basic counting questions: how many vertices does a Vieta graph have, and what is the degree distribution? We focus on explicit counts, addressing the low-dimensional cases in three and four variables.
In 1943, Hadwiger formulated his celebrated conjecture, connecting the chromatic number $\chi(G)$ of a finite, simple, undirected graph with the cardinality of the largest complete minor, $\eta(G)$. The disjoint union of all finite complete graphs shows that Hadwiger's conjecture fails for infinite, but a slightly weaker version is true in these graphs, and open for finite graphs. In this note we generalize that weaker version to hypergraphs and provide a simple, general, and purely set-theoretical formulation of Hadwiger's conjecture.
Since manuscript \cite{R}, recently posted on arXiv, is closely related to our previous work, we would like to clarify some facts about it. Namely, we would like to point out that several results in \cite{R} are already known (Theorem 1 and Corollaries 2, 3 and 4) and some observations regarding our work \cite{FJ} are not correct. We also notice that R\'{e}dei's Theorem, a classical result in graph theory, gives a simple tool to show Theorems 5 and 9.
We prove that the stationary and worst-case expected meeting times of two independent continuous-time random walks on the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ have order $n$ throughout the strictly supercritical, the slightly supercritical and the critical regimes. Using these bounds along with a fine-tuned combination of comparison inequalities due to Oliveira (2012) and Kanade-Mallmann-Trenn-Sauerwald (KMS, 2023), we deduce that expected coalescence time and full voter-model consensus also have order $n$ throughout these three regimes.
Let $\mathcal F=\{2K_2,C_4,C_5\}$, so that $\operatorname{Forb}(\mathcal F)$ is the class of split graphs. Resolving a conjecture of Wang and Tang, we prove that the class of split graphs is generalized spectrally closed and that it admits no walk-realizable $\mathcal F$-supporter of any finite order.
For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a proper partition of the set of triangles in an extremal graph. On the basis of this partition, we obtain the partition of the edge set and thus the structure of an extremal graph. Our new method can also be applied to obtain some meaningful results in other settings.
Xiaojun Zhao, Yuejian Peng· Journal of Graph Theory· 1 citation