2024/06/29 by Jianfeng Hou, Hou, Jianfeng, Yindong Jin +5
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2407.01625
openalex publication_date 2024/06/29 · openalex created_date 2024/07/06 · openalex updated_date 2026/07/28
Let t≥ s≥2 be integers. Confirming a conjecture of Mader, Liu and Montgomery [J. Lond. Math. Soc., 2017] showed that every Ks, t-free graph with average degree d contains a subdivision of a clique with at least Ω(d(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 ((1)/(2) -od(1)) log d. In this paper, we improve this low bound to ((s)/(2(s-1)) -od(1)) log d for Ks, t-free graphs. Both proofs of our results use the graph sublinear expansion property as well as some novel structural techniques.