Balanced clique subdivisions and cycles lengths in $K_{s, t}$-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909044512391168 |
|---|---|
| author | Hou, Jianfeng Jin, Yindong Yang, Donglei Yang, Fan |
| author_facet | Hou, Jianfeng Jin, Yindong Yang, Donglei Yang, Fan |
| contents | Let $ t\ge s\ge2$ be integers. Confirming a conjecture of Mader, Liu and Montgomery [J. Lond. Math. Soc., 2017] showed that every $K_{s, t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $Ω(d^{\frac{s}{2(s-1)}})$ vertices. We give an improvement by showing that such a graph contains a balanced subdivision of a clique with the same order, where a balanced subdivision is a subdivision in which each edge is subdivided the same number of times.
In 1975, Erdős asked whether the sum of the reciprocals of the cycle lengths in a graph with infinite average degree $d$ is necessarily infinite. Recently, Liu and Montgomery [J. Amer. Math. Soc., 2023] confirmed the asymptotically correct lower bound on the reciprocals of the cycle lengths, and provided a lower bound of at least $(\frac{1}{2} -o_d(1)) \log d$. In this paper, we improve this low bound to $\left(\frac{s}{2(s-1)} -o_d(1)\right) \log d$ for $K_{s, t}$-free graphs.
Both proofs of our results use the graph sublinear expansion property as well as some novel structural techniques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01625 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Balanced clique subdivisions and cycles lengths in $K_{s, t}$-free graphs Hou, Jianfeng Jin, Yindong Yang, Donglei Yang, Fan Combinatorics Let $ t\ge s\ge2$ be integers. Confirming a conjecture of Mader, Liu and Montgomery [J. Lond. Math. Soc., 2017] showed that every $K_{s, t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $Ω(d^{\frac{s}{2(s-1)}})$ vertices. We give an improvement by showing that such a graph contains a balanced subdivision of a clique with the same order, where a balanced subdivision is a subdivision in which each edge is subdivided the same number of times. In 1975, Erdős asked whether the sum of the reciprocals of the cycle lengths in a graph with infinite average degree $d$ is necessarily infinite. Recently, Liu and Montgomery [J. Amer. Math. Soc., 2023] confirmed the asymptotically correct lower bound on the reciprocals of the cycle lengths, and provided a lower bound of at least $(\frac{1}{2} -o_d(1)) \log d$. In this paper, we improve this low bound to $\left(\frac{s}{2(s-1)} -o_d(1)\right) \log d$ for $K_{s, t}$-free graphs. Both proofs of our results use the graph sublinear expansion property as well as some novel structural techniques. |
| title | Balanced clique subdivisions and cycles lengths in $K_{s, t}$-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.01625 |