Localized Clique Bounds in Bounded-Degree and Bounded-Path Graphs
Rajat Adak, L. Sunil Chandran · 2025
Read Localized Clique Bounds in Bounded-Degree and Bounded-Path Graphs 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-20946.txt.
Introduction
Rajat Adak and L. Sunil Chandran work on a method called localization, a way to sharpen classic questions about how many copies of a shape a network can contain. In graph theory, such questions ask for the most or fewest copies of a given pattern under set limits. Localization scores the count at each point or link, then adds those local scores up.
That local view recovers old results and often gives tighter bounds. The authors apply it to counts of tight clusters, called cliques, in graphs where each point has few links or where paths stay short. They build on past bounds for such graphs. The work gives mathematicians a general tool for refining limits across many graph problems.
Catalog record
| CREATOR | Rajat Adak, L. Sunil Chandran |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20946
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Localized Clique Bounds in Bounded-Degree and Bounded-Path Graphs Rajat Adak, L. Sunil Chandran Abstract Let ℱ \mathcal{F} be a family of graphs. A graph is said to be ℱ \mathcal{F} -free if it contains no member of ℱ \mathcal{F} . The generalized Turán number e x ( n , H , ℱ ) ex(n,H,\mathcal{F}) denotes the maximum number of copies of a graph H H in an n n -vertex ℱ \mathcal{F} -free graph, while the generalized edge Turán number m e x ( m , H , ℱ ) mex(m,H,\mathcal{F}) denotes the maximum number of copies of H H in an m m -edge ℱ \mathcal{F} -free graph. It is well known that if a graph has maximum degree d d , then it is K 1 , d + 1 K_{1,d+1} -free. Wood [ 16 ] proved that e x ( n , K t , K 1 , d + 1 ) ≤ n d + 1 ( d + 1 t ) ex(n,K_{t},K_{1,d+1})\leq\frac{n}{d+1}\binom{d+1}{t} . More recently, Chakraborty and Chen [ 7 ] established analogous bounds for graphs with bounded maximum path length: m e x ( m , K t , P r + 1 ) ≤ m ( r 2 ) ( r t ) mex(m,K_{t},P_{r+1})\leq\frac{m}{\binom{r}{2}}\binom{r}{t} . In this paper, we improve these bounds using the localization technique, based on suitably defined local parameters. Furthermore, we characterize the extremal graphs attaining these improved bounds. 1 Introduction Extremal graph theory, initiated by Turán, studies the maximum number of edges or subgraphs that a graph can contain while avoiding a prescribed forbidden family. The generalized Turán numbers ex(n,H,\mathcal{F}) and mex(m,H,\mathcal{F}) extend this framework by counting the maximum number of copies of a fixed graph H in \mathcal{F} -free graphs of order n or size m , respectively. These parameters have been studied extensively for natural families such as paths, cycles, and stars. Notation Let N(G,K_{t}) denote the number of subgraphs of G isomorphic to K_{t} . Theorem 1.1 (Wood [ 16 ] ) Let t\geq 1 and G be a graph on n vertices with \Delta(G)=d as the maximum vertex degree, then N(G,K_{t})\leq ex(n,K_{t},K_{1,d+1})\leq\frac{n}{d+1}{d+1\choose t}=\frac{n}{t}{d\choose t-1} If t=1 , we always get equality; otherwise, equality holds if and only if G is a disjoint union of copies of K_{d+1} . Corollary 1 (Wood [ 16 ] ) Let t\geq 1 and G be a graph on n vertices with \Delta(G)=d as the maximum vertex degree, then N(G,K_{\geq 1})\leq\frac{n}{d+1}(2^{d+1}-1) Theorem 1.2 (Chakraborti-Chen [ 7 ] ) Let t\geq 2 and G be a P_{r+1} -free graph on m edges, then N(G,K_{t})\leq mex(m,K_{t},P_{r+1})\leq\frac{m}{{r\choose 2}}{r\choose t} If t=2 , equality always holds; otherwise, equality holds if and only if G is a disjoint union of copies of K_{r} with any number of isolated vertices. 1.1 Localization A classical lower bound for the independence number, \alpha(G) , of a graph G is given by \alpha(G)\geq\frac{n}{\Delta+1} , where n is the number of vertices and \Delta is the maximum degree. This result was generalized by Caro [ 6 ] and Wei [ 15 ] to a local form: \alpha(G)\geq\sum_{v\in V(G)}\frac{1}{d(v)+1} , where d(v) is the degree of vertex v . This generalization shifts the bounds’ dependency from a global graph parameter, \Delta , to a local vertex parameter, d(v) . This raises the question of whether we can apply this same idea of using local parameters to get better results for other graph properties. Bradač [ 5 ] and Malec–Tompkins [ 13 ] recently introduced the idea of localization to strengthen and generalize classical extremal bounds. Classical results typically rely on global parameters, such as the longest path or the circumference of a graph. Localization instead assigns local weights to edges (or vertices), thereby refining global constraints into locally defined ones. For example, one may assign to each edge e the size of the largest clique or the length of the longest path containing e . This framework has led to localized versions of several classical theorems. Bradač [ 5 ] and Malec-Tompkins [ 13 ] introduced a localization of Turán’s theorem [ 14 ] . In [ 13 , 17 ] , the localization approach was further applied to generalize the Erdős–Gallai theorems [ 8 ] for paths and cycles. Kirsch and Nir [ 10 ] established a localized version of Zykov’s generalization of Turán’s theorem, which was subsequently generalized in [ 4 ] , which provided a localization for the Graph Maclaurin Inequalities [ 9 ] . Moreover, the localization framework has also been extended to hypergraphs [ 17 ] and to spectral extremal bounds [ 11 ] . While edge-based localization often produces distribution-type inequalities reminiscent of the LYM or Kraft inequalities, a more direct alternative was proposed in [ 1 ] , where localization is applied to vertices rather than edges. Adak and Chandran [ 1 ] introduced the concept of vertex-based localization . They provided a vertex-based localization of the Erdős–Gallai theorems for paths and cycles. These results yield a more natural and intuitive strengthening of the classical bounds compared to the edge-based approaches of [ 13 , 17 ] . In subsequent work [ 3 ] , the same authors established a vertex-based localization of a popular form of Turán’s theorem, and more recently they extended this framework to generalized Erdős–Gallai theorems due to Luo [ 12 ] , in [ 2 ] . 2 Main Results We provide a vertex-based localization of theorem 2.1 , and to generalize theorem 2.2 , we assign suitable weights to the edges of the graph and apply the localization framework. Theorem 2.1 Let t\geq 1 and G be a simple graph then, N(G,K_{t})\leq\sum_{v\in V(G)}\frac{{d(v)+1\choose t}}{d(v)+1}=\frac{1}{t}\sum_{v\in V(G)}{d(v)\choose t-1} Let X=\{v\in V(G)\mid d(v)+1\geq t\} . If t=1 , equality always holds; otherwise, equality holds if and only if all the components of G[X] are cliques. Corollary 2 Let t\geq 1 and G be a simple graph then, N(G,K_{t\geq 1})\leq\sum_{v\in V(G)}\sum_{t=1}^{d(v)+1}\frac{{d(v)+1\choose t}}{d(v)+1}=\sum_{v\in V(G)}\frac{2^{d(v)+1}-1}{d(v)+1} Notation Define p:E(G)\rightarrow\mathbb{Z} , such that p(e) is the length of the longest path in G containing the edge e . Theorem 2.2 Let t\geq 2 and G be a simple graph, then N(G,K_{t})\leq\sum_{e\in E(G)}\frac{{p(e)+1\choose t}}{{p(e)+1\choose 2}}=\frac{1}{{t\choose 2}}\sum_{e\in E(G)}{p(e)-1\choose t-2} Let Z=\{e\in E(G)\mid p(e)+1<t\} . If t=2 , equality always holds; otherwise, equality holds if and only if all the components of G\setminus Z are cliques. 2.1 Recovering the classical bound From Theorem 2.1 to Theorem 1.1 Since \Delta(G)=d , therefore d\geq d(v) for all v\in V(G) . Thus \frac{1}{t}{d(v)\choose t-1}\leq\frac{1}{t}{d\choose t-1} for all v\in V(G) . Therefore, from the bound of Theorem 2.1 we get; N(G,K_{t})\leq\frac{1}{t}\sum_{v\in V(G)}{d(v)\choose t-1}\leq\frac{1}{t}\sum_{v\in V(G)}{d\choose t-1}=\frac{n}{t}{d\choose t-1} (1) For equality, both the above inequalities must be equalities. Thus G must be d -regular graph. From Theorem 2.1 , the equality holds only if all the components of G[X] are cliques. Therefore, G must be a disjoint union of copies of K_{d+1} . From Theorem 2.2 to Theorem 1.2 Since G is P_{r+1} -free, we get that p(e)+1\leq r for all e\in E(G) . Since p(e)+1\geq 2 we get that, \frac{1}{{t\choose 2}}{p(e)-1\choose t-2}\leq\frac{1}{{t\choose 2}}{r-2\choose t-2}=\frac{{r\choose t}}{{r\choose 2}} . Therefore, from the bound of