A large hole in pseudo-random graphs

Sahar Diskin, Michael Krivelevich, Itay Markbreit, Maksim Zhukovskii · 2025

Read A large hole in pseudo-random graphs by Sahar Diskin, Michael Krivelevich, Itay Markbreit, Maksim Zhukovskii (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23384.txt.

Introduction

Sahar Diskin, Michael Krivelevich, Itay Markbreit, and Maksim Zhukovskii prove that well-mixed graphs must contain a long clean cycle, in work from twenty twenty-five. A clean cycle, or hole, uses graph edges but has no chords across it. The graphs here are pseudo-random, meaning their edges spread in a near-even way. Three values sum up each graph: its size, its degree, and a spread score.

When the spread score is small next to the degree, a long hole must exist. Its length grows with the graph size and shrinks as the degree grows. The team also shows that bound is best possible up to a fixed factor. The same methods count how many distinct inner shapes such graphs must hold. That count grows fast with size, and that growth rate is also shown to be tight.

Catalog record

CREATORSahar Diskin, Michael Krivelevich, Itay Markbreit, Maksim Zhukovskii
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23384

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A large hole in pseudo-random graphs Sahar Diskin, Michael Krivelevich, Itay Markbreit, Maksim Zhukovskii Abstract We show that there exist constants δ 1 , δ 2 > 0 \delta_{1},\delta_{2}>0 such that if G G is an ( n , d , λ ) (n,d,\lambda) -graph with λ / d ≤ δ 1 \lambda/d\leq\delta_{1} , then G G contains an induced cycle of length at least δ 2 ​ n / d \delta_{2}n/d . We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such G G is at least exponential in n ​ log ⁡ d / d n\log d/d , and further demonstrate that this is tight up to a constant factor in the exponent. 1 Introduction and main results The study of extremal problems about induced subgraphs is a popular theme in combinatorics. Of particular interest is finding the lengths of a longest induced path and of a longest induced cycle (also called a hole ) in a given graph G . Two key examples, that have been studied in the past, are when G is the d -dimensional hypercube, wherein finding the length of a longest induced path is known as the ‘Snake-in-the-Box’ problem [ 1 , 25 ] , and when G is the binomial random graph G(n,p) . Let us note here that the length of a longest induced path is at most twice the size of a largest independent set in G . The study of induced cycles in G(n,p) dates back to the late ’80s. Frieze and Jackson [ 15 ] showed that for each sufficiently large constant d , whp 1 1 1 With high probability, that is, with probability tending to one as n tends to infinity the random graph G(n,d/n) contains an induced cycle of length at least c(d)\,n for some constant c(d)>0 . Łuczak [ 22 ] and, independently, Suen [ 24 ] later improved this, proving that whenever d>1 , whp G(n,d/n) contains an induced cycle of length at least (1+o(1))\frac{\ln d}{d}\,n . A simple first‑moment argument implies that whp the length of a longest induced cycle for large d in G(n,d) is at most (1+o_{d}(1))\frac{2\ln d}{d}\,n . This upper bound was shown to be asymptotically tight by Draganić, Glock, and Krivelevich [ 9 ] . Dutta and Subramanian [ 11 ] further established a two-point concentration result on the length of a longest induced path in G(n,p) for p\geq\log^{2}n/\sqrt{n} . It appears natural to extend the study of extremal problems for induced paths and cycles for random to pseudo-random graphs. The latter can be informally described as graphs whose edge distribution resembles that of a truly random graph G(n,p) of a similar density. Formally, given a d -regular graph G on n vertices, denote the eigenvalues of its adjacency matrix by d=\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n} . Letting \lambda\coloneqq\max\{|\lambda_{2}|,|\lambda_{n}|\} , we then say that G is an (n,d,\lambda) -graph. The expander mixing lemma, due to Alon and Chung [ 3 ] , relates the spectral ratio \frac{\lambda}{d} to the edge-distribution of these graphs (see Lemma 2.2 ). We refer the reader to [ 16 , 18 , 19 ] for comprehensive surveys on the subject of pseudo-random graphs and expanders. As noted before, it is thus quite natural to ask whether one can find long induced cycles, similar to the case of the binomial random graph G(n,d/n) , in (n,d,\lambda) -graphs (naturally under some assumption on the aforementioned spectral ratio). A first result in this direction was recently obtained by Draganić and Keevash [ 10 ] , who showed the following: any (n,d,\lambda) -graph G with \lambda<d^{3/4}/100 and d<n/10 contains an induced path of length \frac{n}{64d} ; their paper did not address the problem of long induced cycles. Our first main result improves upon the result of Draganić and Keevash [ 10 ] by significantly relaxing the assumption on the spectral ratio, as well as showing the existence of a long induced cycle , instead of a path. Theorem 1 . There exist constants \delta_{1},\delta_{2},\delta_{3}>0 such that the following holds. For any integers n,d and for any (n,d,\lambda) -graph G such that d\leq\delta_{3}n and \lambda/d\leq\delta_{1} , G contains an induced cycle of length at least \delta_{2}n/d . A few comments are in place. We note that for \delta_{1} sufficiently small, one can take \delta_{2}=1/150 ; in fact, as we will soon see, we can find a longer induced path , of length at least \frac{n}{48d} , thus improving also the constant factor in the result of [ 10 ] . Further, since a random d -regular graph on n vertices G_{n,d} is typically an (n,d,\lambda) -graph with \lambda\leq 2\sqrt{d} (see, e.g., [ 13 ] ), we obtain that for large enough d , whp G_{n,d} contains an induced cycle of length \Omega(n/d) . This improves the bound of Frieze and Jackson [ 15 ] from 1985, who showed that whp G_{n,d} contains an induced cycle of length \Omega(n/d^{2}) (see also [ 12 ] ), and makes progress towards resolving [ 14 , Problem 74] , which asks to determine the typical length of a longest induced cycle in G_{n,d} . Finally, let us note that our proof yields a randomised algorithm, which finds in a linear in n time an induced cycle of length at least \delta_{2}n/d whp . It turns out, perhaps somewhat surprisingly, that insights and results from the setting of site percolation prove very efficient, leading to a rather simple (in hindsight) proof of Theorem 1 . Intuitively, finding an induced cycle is ’easier’ when the graph is sparse, and in this case, choosing a random set of vertices typically yields a sparser graph, wherein every induced structure is also an induced structure in the host graph. Formally, given a host graph G=(V,E) , form a random subset V_{p} by retaining every v\in V independently with probability p . The p -site-percolated 2 2 2 In many papers, this notation is reserved for the bond -percolated random subgraph. Throughout this paper, we reserve G_{p} for the p - site -percolated random subgraph. subgraph G_{p} is then G_{p}\coloneqq G[V_{p}] . We will derive Theorem 1 from our next result. Theorem 2 . Let \epsilon>0 be a sufficiently small constant. Let n,d\coloneqq d(n)\in\mathbb{N} be such that d=o(n) . Let p=\frac{1+\epsilon}{d} . Then, there exists a constant \delta\coloneqq\delta(\epsilon)>0 such that the following holds. Let G be an (n,d,\lambda) -graph with \frac{\lambda}{d}\leq\delta . Then, whp G_{p} contains an induced path of length at least \frac{\epsilon^{2}n}{3d} . Note that Theorem 2 naturally implies that deterministically the whole graph G contains a long induced path. In fact, with a little more effort, one can typically find an induced cycle of length \Omega(n/d) in G_{p} , see details in Remark 3.1 . Further, as we mentioned after Theorem 1 , it is not hard to verify that one can take any \epsilon\leq 1/4 , and thus obtain an induced path of length \frac{n}{48d} . Since the edge-distribution of an (n,d,\lambda) -graph G (when \lambda/d\leq\delta for some sufficiently small constant \delta ) resembles that of the binomial random graph G(n,d/n) , one might expecto to find an induced path (or

Read the complete text