How connectivity affects the extremal number of trees

EUROCOMB’23

Abstract
The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree $T$, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$.

Pages:
623–631
References

Paul N. Balister, Ervin Győri, Jenő Lehel, and Richard H. Schelp. Connected graphs without long paths. Discrete Mathematics, 308(19):4487-4494, 2008.
https://doi.org/10.1016/j.disc.2007.08.047

Guido Besomi, Matías Pavez-Signé, and Maya Stein. On the Erdős-Sós conjecture for trees with bounded degree. Combinatorics, Probability and Computing, 30(5):741-761, 2021.
https://doi.org/10.1017/S0963548320000528

Stephan Brandt and Edward Dobson. The Erdős-Sós conjecture for graphs of girth 5. Discrete Mathematics, 150:411-414, 1996.
https://doi.org/10.1016/0012-365X(95)00207-D

Yair Caro, Balázs Patkós, and Zsolt Tuza. Connected Turán number of trees. arXiv preprint arXiv:2208.06126, 2022.

Guantao Chen, Ronald J. Gould, Florian Pfender, and Bing Wei. Extremal graphs for intersecting cliques. Journal of Combinatorial Theory, Series B, 89:159-171, 2003.
https://doi.org/10.1016/S0095-8956(03)00044-3

Paul Erdős and A. H. Stone. On the structure of linear graphs. Bulletin of the American Mathematical Society, 52:1087-1091, 1946.
https://doi.org/10.1090/S0002-9904-1946-08715-7

Paul Erdős. Extremal problems in graph theory. In Theory of graphs and its applications (Proc. Sympos. Smolenice, 1963), pages 29-36. Publishing House of the Czechoslovak Academy of Science, Prague, 1964.

Paul Erdős, Z. Füredi, Ronald J. Gould, and D. S. Gunderson. Extremal graphs for intersecting triangles. Journal of Combinatorial Theory, Series B, 64:89-100, 1995.
https://doi.org/10.1006/jctb.1995.1026

Paul Erdős and Tibor Gallai. On maximal paths and circuits of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 10(3-4):337-356, 1959.
https://doi.org/10.1007/BF02024498

Paul Erdős and Miklós Simonovits. A limit theorem in graph theory. Studia Scientiarum Mathematicarum Hungarica, 1:51-57, 1966.

Genghua Fan, Xuezheng Lv, and Pei Wang. Cycles in 2-connected graphs. Journal of Combinatorial Theory, Series B, 92(2):379-394, 2004.
https://doi.org/10.1016/j.jctb.2004.09.003

Ralph J. Faudree and Richard H. Schelp. Path Ramsey numbers in multicolorings. Journal of Combinatorial Theory, Series B, 19(2):150-160, 1975.
https://doi.org/10.1016/0095-8956(75)90080-5

Zoltán Füredi, Alexandr Kostochka, Ruth Luo, and Jacques Verstraëte. Stability in the Erdős-Gallai theorem on cycles and paths, II. Discrete Mathematics, 341(5):1253-1263, 2018.
https://doi.org/10.1016/j.disc.2017.12.018

Zoltán Füredi, Alexandr Kostochka, and Jacques Verstraëte. Stability in the Erdős-Gallai theorems on cycles and paths. Journal of Combinatorial Theory, Series B, 121:197-228, 2016.
https://doi.org/10.1016/j.jctb.2016.06.004

Zoltán Füredi and Miklós Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, pages 169-264. Springer, 2013.
https://doi.org/10.1007/978-3-642-39286-3_7

Dániel Gerbner, Abhishek Methuku, and Cory Palmer. General lemmas for Berge-Turán hypergraph problems. European Journal of Combinatorics, 86:103082, 2020.
https://doi.org/10.1016/j.ejc.2020.103082

Agnieszka Görlich and Andrzej Żak. On Erdős-Sós conjecture for trees of large size. The Electronic Journal of Combinatorics, 23(1):#P1.52, 2016.
https://doi.org/10.37236/5405

Ervin Győri, Nika Salia, Casey Tompkins, and Oscar Zamora. Turán numbers of Berge trees. Discrete Mathematics, 346(4):113286, 2023.
https://doi.org/10.1016/j.disc.2022.113286

G. N. Kopylov. On maximal paths and cycles in a graph. Doklady Akademii Nauk SSSR, 234(1):19-21, 1977.

Bernard Lidický, Hong Liu, and Cory Palmer. On the Turán number of forests. The Electronic Journal of Combinatorics, 20(2):#P62, 2013.
https://doi.org/10.37236/3142

Andrew McLennan. The Erdős-Sós conjecture for trees of diameter four. Journal of Graph Theory, 49(4):291-301, 2005.
https://doi.org/10.1002/jgt.20083

Václav Rozhoň. A local approach to the Erdős-Sós conjecture. SIAM Journal on Discrete Mathematics, 33(2):643-664, 2019.
https://doi.org/10.1137/18M118195X

Jean-François Saclé and Mariusz Woźniak. The Erdős-Sós conjecture for graphs without C4. Journal of Combinatorial Theory, Series B, 70:367-372, 1997.
https://doi.org/10.1006/jctb.1997.1758

Nika Salia, Casey Tompkins, and Oscar Zamora. An Erdős-Gallai type theorem for vertex colored graphs. Graphs and Combinatorics, 35(3):689-694, 2019.
https://doi.org/10.1007/s00373-019-02026-1

D. R. Woodall. Maximal circuits of graphs. I. Acta Mathematica Academiae Scientiarum Hungarica, 28(1-2):77-80, 1976.
https://doi.org/10.1007/BF01902497

Mariusz Woźniak. On the Erdős-Sós conjecture. Journal of Graph Theory, 21(2):229-234, 1996.
https://doi.org/10.1002/(SICI)1097-0118(199602)21:2<229::AID-JGT13>3.0.CO;2-E

Long-Tu Yuan. Extremal graphs for edge blow-up of graphs. Journal of Combinatorial Theory, Series B, 152:379-398, 2022
https://doi.org/10.1016/j.jctb.2021.10.006

Metrics

0

Views

0

PDF views