We show that, for some absolute constants $c_1,c_2>0$, every $(n,d,\lambda)$-graph with $\lambda\le c_1 d$ contains an induced cycle of length at least $c_2n\log(d/\lambda)/d$. This is best possible up to the values of $c_1,c_2$. Our techniques include a multi-scale algorithmic analysis, an adapted depth-first exploration procedure, a link to percolation theory, and estimates for random row-and-column extraction in symmetric matrices.
We show that if an $(n,d,\lambda)$-graph satisfies $\lambda\leq (1-\delta)d$ and $d\gg \delta^{-6}(\log n)^{3}$ for some $\delta>0$, then it is Hamiltonian. A qualitatively similar result was recently proven by Brada\v{c} and Janzer. Our proof here is shorter and gives better quantitative bounds. \par In our proof, as...
Let $G_{n,d}$ be a uniformly random simple $d$-regular graph on $n$ vertices, and let $A_n$ be its adjacency matrix. For every fixed $\lambda\in(0,1/2)$, we prove that for any $\lambda(n-1)\le d\le(1-\lambda)(n-1)$, $\mathbb P(A_n\text{ is singular})\le e^{-cn}$, where $c>0$ depends only on $\lambda$, and $n$ is suffic...
Ze-Yan Song, Han-Chao Wang, Sheng-Yan Yin et al.· 0 citations
After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.
J'ozsef Balogh, Andrzej Grzesik, Bernard Lidický et al.· 0 citations
We prove that the domination number of the $2$-token graph of the path $P_n$ is $\gamma(F_2(P_n))=d(n)$ for every $n\ge 13$, where $d(n)=\frac1{10}(n^2+5n+c)$ and $c$ is an explicit constant that depends on $n \bmod 5$. This settles a conjecture by Lea\~nos and the authors, who previously proved the upper bound. The lo...
We extend the hypergraph regularity method to sparse $3$-uniform hypergraphs whose vertex links are $C_4$-free. In other words, we consider hypergraphs $H=(V,E)$ that are $K_{1,2,2}$-free, which implies that $|E|=O(|V|^{5/2})$. For such hypergraphs we establish a sparse analogue of the removal lemma for the tight cycle...
Ayush Basu, C. Reiher, V. Rödl et al.· 0 citations
We prove that there is an absolute constant $c>0$ such that every connected vertex-transitive graph $G$ on $n \ge 3$ vertices contains a cycle of length at least $cn$. Moreover, every such graph with sufficiently large degree $d$ contains a cycle of length at least $(1-d^{-1/100})n$. This gives the first linear bound t...
Jie Ma, Zi-Yuan Zhao· 1 citation· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
