Vertex-Based Localization of generalized Turán Problems

Rajat Adak, L. Sunil Chandran · 2025

Read Vertex-Based Localization of generalized Turán Problems by Rajat Adak, L. Sunil Chandran (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-2508-20936.txt.

Introduction

Rajat Adak and Sunil Chandran sharpen bounds in extremal graph theory in this 2025 paper. Generalized Turán problems ask how many copies of a pattern graph can fit in a network that avoids a forbidden family. Classic results bound the total by network size alone.

Their vertex-based method refines the count vertex by vertex, using the longest path or cycle through each point. Summing those local terms yields stronger global bounds than earlier path and cycle results. They also characterize the graphs that meet the bounds exactly, proving most cases and reducing one to earlier work. A generalization of a known result by four other authors follows as well. The framework localizes a global counting problem.

Catalog record

CREATORRajat Adak, L. Sunil Chandran
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20936

Browse the full library · About the Tower of Babel

Full text

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

Vertex-Based Localization of generalized Turán Problems Rajat Adak, L. Sunil Chandran Abstract Let ℱ \mathcal{F} be a family of graphs. A graph is called ℱ \mathcal{F} -free if it does not contain any member of ℱ \mathcal{F} . Generalized Turán problems aim to maximize the number of copies of a graph H H in an n n -vertex ℱ \mathcal{F} -free graph. This maximum is denoted by e ​ x ​ ( n , H , ℱ ) ex(n,H,\mathcal{F}) . When H ≅ K 2 H\cong K_{2} , it is simply denoted by e ​ x ​ ( n , F ) ex(n,F) . Erdős and Gallai established the bounds e ​ x ​ ( n , P k + 1 ) ≤ n ⁡ ( k − 1 ) 2 ex(n,P_{k+1})\leq\frac{n(k-1)}{2} and e ​ x ​ ( n , C ≥ k + 1 ) ≤ k ⁡ ( n − 1 ) 2 ex(n,C_{\geq k+1})\leq\frac{k(n-1)}{2} . This was later extended by Luo [ 12 ] , who showed that e ​ x ​ ( n , K s , P k + 1 ) ≤ n k ​ ( k s ) ex(n,K_{s},P_{k+1})\leq\frac{n}{k}\binom{k}{s} and e ​ x ​ ( n , K s , C ≥ k + 1 ) ≤ n − 1 k − 1 ​ ( k s ) ex(n,K_{s},C_{\geq k+1})\leq\frac{n-1}{k-1}\binom{k}{s} . Let N ⁡ ( G , K s ) N(G,K_{s}) denote the number of copies of K s K_{s} in G G . In this paper, we use the vertex-based localization framework, introduced in [ 2 ] , to generalize Luo’s bounds. In a graph G G , for each v ∈ V ⁡ ( G ) v\in V(G) , define p ⁡ ( v ) p(v) to be the length of the longest path that contains v v . We show that N ⁡ ( G , K s ) ≤ ∑ v ∈ V ⁡ ( G ) 1 p ⁡ ( v ) + 1 ​ ( p ⁡ ( v ) + 1 s ) = 1 s ​ ∑ v ∈ V ⁡ ( G ) ( p ⁡ ( v ) s − 1 ) N(G,K_{s})\leq\sum_{v\in V(G)}\frac{1}{p(v)+1}{p(v)+1\choose s}=\frac{1}{s}\sum_{v\in V(G)}{p(v)\choose s-1} We strengthen the cycle bound from [ 12 ] as follows: In graph G G , for each v ∈ V ⁡ ( G ) v\in V(G) , let c ⁡ ( v ) c(v) be the length of the longest cycle that contains v v , or 2 2 if v v is not part of any cycle. We prove that N ⁡ ( G , K s ) ≤ ( ∑ v ∈ V ⁡ ( G ) 1 c ⁡ ( v ) − 1 ​ ( c ⁡ ( v ) s ) ) − 1 c ⁡ ( u ) − 1 ​ ( c ⁡ ( u ) s ) N(G,K_{s})\leq\left(\sum_{v\in V(G)}\frac{1}{c(v)-1}{c(v)\choose s}\right)-\frac{1}{c(u)-1}{c(u)\choose s} where c ⁡ ( u ) c(u) denotes the circumference of G G . Furthermore, we characterize the class of extremal graphs that attain equality for these bounds. We provide full proofs for the cases s = 1 s=1 and s ≥ 3 s\geq 3 , while the case s = 2 s=2 follows from the result in [ 2 ] . Keywords: Generalized Turán Problems, Vertex-Based Localization, Erdős-Gallai Theorems 1 Introduction In recent years, there has been growing interest in generalized Turán problems, which focus on determining the maximum number of copies of a fixed graph H that a graph on n vertices can contain under various constraints. This line of inquiry can be traced back to the classical theorem of Turán [ 14 ] , where H is assumed to be an edge, in which cases, the goal is just maximizing the number of edges in a n -vertex graph under the given constraints; the maximum value in this case is referred to as the Turán number of n for the given constraint. 1.1 Classical Turán problems A graph is said to be \mathcal{F} -free if it contains no members of the family \mathcal{F} as a subgraph. The Turán number of such a graph on n vertices is denoted by ex(n,T) . A classical example of a Turán problem was given by Erdős and Gallai [ 8 ] , who studied the Turán numbers of graphs that avoid long paths and long cycles — that is, ex(n,P_{k+1}) and ex(n,C_{\geq k+1}) , where P_{k+1} is the path on k+1 vertices and C_{\geq k+1} denotes any cycle of length at least k+1 . Theorem 1.1 . (Erdős-Gallai [ 8 ] ) For a simple graph G with n vertices without a path of length k(\geq 1) , that is a path with k edges (P_{k+1}) , |E(G)|\leq ex(n,P_{k+1})\leq\frac{n(k-1)}{2} and equality holds if and only if all the components of G are complete graphs of order k . Theorem 1.2 . (Erdős-Gallai [ 8 ] ) For a simple graph G with n vertices and circumference (length of the longest cycle in the graph) at most k , |E(G)|\leq ex(n,C_{\geq k+1})\leq\frac{k(n-1)}{2} and equality holds if and only if G is connected and all its blocks are complete graphs of order k . 1.2 Generalized Turán problems The maximum number of copies of a graph H in an n -vertex, \mathcal{F} -free graph is denoted by ex(n,H,\mathcal{F}) . Luo [ 12 ] extended 1.1 and 1.2 by providing a generalized Turán-type version of the Erdős–Gallai theorems. Recently, Chakraborti and Chen [ 7 ] classified the extremal graphs for these bounds. Notation . Let N(G,K_{s}) denote the number of subgraphs of G isomorphic to K_{s} . Theorem 1.3 . (Luo [ 12 ] ) For a simple graph G with n vertices without a path of length k(\geq 1) , N(G,K_{s})\leq ex(n,K_{s},P_{k+1})\leq\frac{n}{k}{k\choose s} and equality holds if and only if all the components of G are complete graphs of order k . Remark 1.4 . Note that taking s=2 , we get back 1.1 . Theorem 1.5 . (Luo [ 12 ] ) For a simple graph G with n vertices and circumference at most k , N(G,K_{s})\leq ex(n,K_{s},C_{\geq k+1})\leq\frac{n-1}{k-1}{k\choose s} and equality holds if and only if G is connected, and all its blocks are complete graphs of order k . Remark 1.6 . Note that if we take s=2 , we get back 1.2 . 1.3 Localization Recently, Bradač [ 6 ] and Malec and Tompkins [ 13 ] introduced the concept of localization as a means to strengthen and generalize classical extremal graph bounds. The classical extremal bounds rely on global parameters; for example, the length of the longest path in 1.1 , or the circumference in 1.2 . The localization framework begins by introducing a localization function that captures global graph parameters in a locally defined manner. For instance, while the clique number of a graph G is a global property, we can localize it by defining a function w:E(G)\rightarrow\mathbb{Z} , where w(e) denotes the size of the largest clique containing the edge e . Localization replaces global constraints with local weight functions, defined over specific graph parameters such as edges or vertices. Thus far, most

Read the complete text