On 2 2 -connected graphs avoiding cycles of length 0 0 modulo 4 4

Hojin Chu, Boram Park, Homoon Ryu · 2025

Read On 2 2 -connected graphs avoiding cycles of length 0 0 modulo 4 4 by Hojin Chu, Boram Park, Homoon Ryu (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-2507-12798.txt.

Introduction

Hojin Chu, Boram Park, and Homoon Ryu settle a counting question about networks that avoid cycles of one special length class. A cycle's length class here means lengths that divide evenly by four. Past work found the most edges an n-point network can have with no such cycle, but the networks reaching that bound all fall apart when one point is removed.

The authors ask for the bound among tougher networks, ones that stay in one piece after any single point is removed. They prove such a network has at most a bound of about one and a half edges per point. They also give a recipe that builds endless examples reaching the bound exactly. The result adds a sharp data point to extremal graph theory, the study of how much structure a network can have while avoiding a pattern.

Catalog record

CREATORHojin Chu, Boram Park, Homoon Ryu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12798

Browse the full library · About the Tower of Babel

Full text

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

On 2 2 -connected graphs avoiding cycles of length 0 0 modulo 4 4 Hojin Chu, Boram Park, Homoon Ryu Abstract For two integers k k and ℓ \ell , an ( ℓ ​ mod ​ k ) (\ell\text{ mod }k) -cycle means a cycle of length m m such that m ≡ ℓ ( mod k ) m\equiv\ell\pmod{k} . In 1977, Bollobás proved a conjecture of Burr and Erdős by showing that if ℓ \ell is even or k k is odd, then every n n -vertex graph containing no ( ℓ ​ mod ​ k ) (\ell\text{ mod }k) -cycles has at most a linear number of edges in terms of n n . Since then, determining the exact extremal bounds for graphs without ( ℓ ​ mod ​ k ) (\ell\text{ mod }k) -cycles has emerged as an interesting question in extremal graph theory, though the exact values are known only for a few integers ℓ \ell and k k . Recently, Győri, Li, Salia, Tompkins, Varga and Zhu proved that every n n -vertex graph containing no ( 0 ​ mod ​ 4 ) (0\text{ mod }4) -cycles has at most ⌊ 19 12 ​ ( n − 1 ) ⌋ \left\lfloor\frac{19}{12}(n-1)\right\rfloor edges, and they provided extremal examples that reach the bound, all of which are not 2 2 -connected. In this paper, we show that a 2 2 -connected graph without ( 0 ​ mod ​ 4 ) \mathrm{(}0\mathrm{\ mod\ 4)} -cycles has at most ⌊ 3 ​ n − 1 2 ⌋ \left\lfloor\frac{3n-1}{2}\right\rfloor edges, and this bound is tight by presenting a method to construct infinitely many extremal examples. 1 Introduction All graphs in the paper are simple. We denote by e(G) the number of edges in a graph G . For two integers k and \ell , an (\ell\text{ mod }k) -cycle or (\ell\text{ mod }k) -path means a cycle or path of length m such that m\equiv\ell\pmod{k} . Burr and Erdős [ 6 ] conjectured that if an n -vertex graph does not contain an (\ell\text{ mod }k) -cycle, where k\mathbb{Z}+\ell contains an even number, then it has at most a linear number of edges in terms of n . This conjecture was later confirmed by Bollobás [ 2 ] , whose result naturally led to the following question: What is the smallest constant c_{\ell,k} , where k\mathbb{Z}+\ell contains an even number, such that every n -vertex graph with c_{\ell,k}n edges contains an ( \ell mod k )-cycle? This problem has received significant attention, and some improvements to the general bounds on c_{\ell,k} have been made. In particular, Sudakov and Verstraëte [ 13 ] showed that for 3\leq\ell<k , the value of c_{\ell,k} is proportional to the maximum average degree of a k -vertex graph without cycles of length \ell . This determines c_{\ell,k} up to an absolute constant. Moreover, for even \ell\geq 4 , determining c_{\ell,k} is as hard as determining the Turán number for even cycles. As a consequence, the exact asymptotics of c_{\ell,k} are known up to constants only for \ell\in\{4,6,10\} or \ell=\Omega(\log k) . The exact value of c_{\ell,k} is known only for a few specific values of \ell and k . It is well known that c_{0,2}=\frac{3}{2} . Chen and Saito [ 3 ] proved that c_{0,3}=2 and the extremal graphs are K_{2,n-2} . Bai, Li, Pan and Zhang [ 1 ] proved that c_{1,3}=\frac{5}{3} , and one vertex identifications of Petersen graphs are extremal graphs. Dean, Kaneko, Ota and Toft [ 4 ] , as well as Saito [ 12 ] , showed that c_{2,3}=3 , with extremal graphs being K_{3,n-3} . In the case of (\ell\bmod 4) -cycles, there has been substantial recent progress, and several noteworthy results have been announced. In [ 8 ] , Gao, Li, Ma and Xie proved that an n -vertex graph with at least \frac{5(n-1)}{2} edges contains two consecutive even cycles unless 4\mid(n-1) and every block is isomorphic to K_{5} . This result not only shows that c_{2,4}=\frac{5}{2} , but also resolves a special case of a conjecture by Verstraëte [ 14 ] on extremal graphs avoiding k cycles of consecutive lengths. Most recently, the result was extended by Li, Pan and Shi [ 10 ] , considering Sudakov-Verstraëte’s conjecture in [ 13 ] . In [ 9 ] , Győri, Li, Salia, Tompkins, Varga and Zhu determined that c_{0,4}=\frac{19}{12} , as stated below, and the paper discusses extremal graphs achieving the bound, the examples given in [ 9 ] are not 2 -connected. Theorem 1.1 ( [ 9 ] ) . Let G be an n -vertex graph. If e(G)>\left\lfloor\frac{19}{12}(n-1)\right\rfloor , then G contains a \mathrm{(}0\mathrm{\ mod\ 4)} -cycle. When the known extremal graphs have cut-vertices, it naturally motivates the study of the extremal problem within the class of 2 -connected graphs. This line of research is considered an interesting and meaningful study. For example, in [ 7 ] , Fan, Lv and Wang considered the extremal problem about 2-connected graphs avoiding a cycle of length at least c for some given integer c , since the extremal graphs avoiding a cycle of length at least c on general graphs have cut-vertices. In this paper, we study the extremal problem of avoiding (0\text{ mod }4) -cycles in the class of 2 -connected graphs. Dean, Lesniak and Saito [ 5 ] showed that every 3 -connected graph always contains a (0\text{ mod }4) -cycle. As it was noted above, the extremal examples given in [ 9 ] are not 2 -connected, which immediately leads to the following question: What is the maximum number of edges in a 2 -connected graph that avoids (0\text{ mod }4) -cycles? Our main result gives a complete answer to this question as follows. Theorem 1.2 . Let G be a 2 -connected n -vertex graph. If e(G)>\left\lfloor\frac{3n-1}{2}\right\rfloor , then G contains a \mathrm{(}0\mathrm{\ mod\ 4)} -cycle. The bound in Theorem 1.2 is tight in the sense that we can construct infinitely many 2 -connected n -vertex graphs with exactly \left\lfloor\frac{3n-1}{2}\right\rfloor edges that contain no \mathrm{(}0\mathrm{\ mod\ 4)} -cycles, when n\geq 12 (see Section 4). The paper is organized as follows. Section 2 collects some definitions, observations, and states some known propositions. Section 3 gives a proof of Theorem 1.2 , and Section 4 describes the extremal graphs. 2 Preliminaries 2.1 Basic definitions and notations For a path P:v_{0}v_{1}\cdots v_{m} , the subpath v_{i}v_{i+1}\cdots v_{j} of P is denoted by P[v_{i},v_{j}] . When C:v_{0}v_{1}\cdots v_{m}v_{0} is a cycle, the path v_{i}v_{i+1}\cdots v_{i+j} , where the subscripts are taken modulo m+1 , is denoted by C[v_{i},v_{i+j}] . For a walk W:v_{0}v_{1}\cdots v_{m} , \overleftarrow{W} means a walk v_{m}\cdots v_{1}v_{0} obtained by reversing W . The length of a walk W is the number of edges in W , denoted by \ell(W) . For two walks P and Q , if the terminal vertex of P and the initial vertex of Q are the same, then P+Q denotes a walk along P and Q . For two vertex sets X and Y of a graph, a path P is called an (X,Y) -path if one end of P is contained in X , the other is contained

Read the complete text