Localization: A Framework to Generalize Extremal Graph Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914379107139584 |
|---|---|
| author | Adak, Rajat Chandran, L. Sunil |
| author_facet | Adak, Rajat Chandran, L. Sunil |
| contents | Extremal graph theory studies the maximum or minimum number of subgraphs isomorphic to a prescribed graph under given constraints. \textit{Localization} has recently emerged as a framework that refines such problems by assigning extremal quantities locally (to vertices or edges) and then aggregating them. This perspective not only recovers classical results but also leads to sharper bounds.
A classical result states that a connected planar graph with a finite girth $g$ satisfies \begin{equation*}
m \leq \frac{g}{g-2}(n-2) \end{equation*} Wood~\cite{wood} derived upper bounds on the number of $K_t$-cliques in graphs of bounded maximum degree, expressed in terms of both the number of vertices and the number of edges: \begin{align*}
ex(n,K_t,K_{1,d+1}) \leq \frac{n}{d+1}\binom{d+1}{t} \\ mex(m,K_t,K_{1,d+1}) \leq \frac{m}{\binom{d+1}{2}}\binom{d+1}{t} \end{align*} More recently, Chakraborty and Chen~\cite{CHAKRABORTI2024103955} established a similar upper bound for graphs with bounded path length: \begin{equation*}
mex(m,K_t,P_{r+1}) \leq \frac{m}{\binom{r}{2}}\binom{r}{t} \end{equation*}
In this paper, we employ the localization framework to improve these bounds and provide structural characterizations of the extremal graphs attaining them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20946 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Localization: A Framework to Generalize Extremal Graph Problems Adak, Rajat Chandran, L. Sunil Combinatorics Discrete Mathematics Extremal graph theory studies the maximum or minimum number of subgraphs isomorphic to a prescribed graph under given constraints. \textit{Localization} has recently emerged as a framework that refines such problems by assigning extremal quantities locally (to vertices or edges) and then aggregating them. This perspective not only recovers classical results but also leads to sharper bounds. A classical result states that a connected planar graph with a finite girth $g$ satisfies \begin{equation*} m \leq \frac{g}{g-2}(n-2) \end{equation*} Wood~\cite{wood} derived upper bounds on the number of $K_t$-cliques in graphs of bounded maximum degree, expressed in terms of both the number of vertices and the number of edges: \begin{align*} ex(n,K_t,K_{1,d+1}) \leq \frac{n}{d+1}\binom{d+1}{t} \\ mex(m,K_t,K_{1,d+1}) \leq \frac{m}{\binom{d+1}{2}}\binom{d+1}{t} \end{align*} More recently, Chakraborty and Chen~\cite{CHAKRABORTI2024103955} established a similar upper bound for graphs with bounded path length: \begin{equation*} mex(m,K_t,P_{r+1}) \leq \frac{m}{\binom{r}{2}}\binom{r}{t} \end{equation*} In this paper, we employ the localization framework to improve these bounds and provide structural characterizations of the extremal graphs attaining them. |
| title | Localization: A Framework to Generalize Extremal Graph Problems |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2508.20946 |