Extremal number of graphs from geometric shapes

EUROCOMB’23

Jun Gao Oliver Janzer Hong Liu Zixiang Xu

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-064

PDF
Abstract
We study the Turán problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature. (i) The prism $C_{2\ell}^{\square}:=C_{2\ell}\square K_{2}$ is the graph consisting of two vertex disjoint $2\ell$-cycles and a matching pairing the corresponding vertices of these two cycles. We show that for every $\ell\ge 4$, ex$(n,C_{2\ell}^{\square})=\Theta(n^{3/2})$. This resolves a conjecture of He, Li and Feng. (ii) The hexagonal tiling in honeycomb is one of the most natural structures in the real world. We show that the extremal number of honeycomb graphs has the same order of magnitude as their basic building unit 6-cycles. (iii) We also consider bipartite graphs from quadrangulations of the cylinder and the torus. We prove near optimal bounds for both configurations. In particular, our method gives a very short proof of a tight upper bound for the extremal number of the 2-dimensional grid, improving a recent result of Bradač, Janzer, Sudakov and Tomon. Our proofs mix several ideas, including shifting embedding schemes, weighted homomorphism and subgraph counts and asymmetric dependent random choice.

Pages:
463–470
References

Noga Alon, Michael Krivelevich, and Benny Sudakov. Turán numbers of bipartite graphs and related Ramsey-type questions. Combinatorics, Probability and Computing, 12(5-6):477-494, 2003.
https://doi.org/10.1017/S0963548303005741

Noga Alon, Lajos Rónyai, and Tibor Szabó. Norm-graphs: variations and applications. J. Combin. Theory Ser. B, 76(2):280-290, 1999.
https://doi.org/10.1006/jctb.1999.1906

J. A. Bondy and M. Simonovits. Cycles of even length in graphs. J. Combin. Theory Ser. B, 16:97-105, 1974.
https://doi.org/10.1016/0095-8956(74)90052-5

Domagoj Bradač, Oliver Janzer, Benny Sudakov, and István Tomon. The Turán number

of the grid. Bull. Lond. Math. Soc., 55:194-204, 2023. 7
https://doi.org/10.1112/blms.12721

W. G. Brown. On graphs that do not contain a Thomsen graph. Canadian Mathematical Bulletin, 9(3):281-285, 1966.
https://doi.org/10.4153/CMB-1966-036-2

Boris Bukh. Extremal graphs without exponentially-small bicliques. arXiv preprint, arXiv: 2109.04167, 2021.

P. Erdős. Problems and results in graph theory. In The theory and applications of graphs (Kalamazoo, Mich., 1980), pages 331-341. Wiley, New York, 1981.

P. Erdős, A. Rényi, and V. T. Sós. On a problem of graph theory. Studia Sci. Math. Hungar., 1:215-235, 1966.

P. Erdős and M. Simonovits. A limit theorem in graph theory. Studia Sci. Math. Hungar., 1:51-57, 1966.

P. Erdős and M. Simonovits. Some extremal problems in graph theory. In Combinatorial theory and its applications, I (Proc. Colloq., Balatonfüred, 1969), pages 377-390. North-

Holland, Amsterdam, 1970.

P. Erdős and M. Simonovits. An extremal graph problem. Acta Math. Acad. Sci. Hungar., 22:275-282, 1971/72.
https://doi.org/10.1007/BF01896420

P. Erdős and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc., 52:1087-1091, 1946.
https://doi.org/10.1090/S0002-9904-1946-08715-7

Zoltán Füredi and Miklós Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erdős centennial, volume 25 of Bolyai Soc. Math. Stud., pages 169-264. János Bolyai Math. Soc., Budapest, 2013.
https://doi.org/10.1007/978-3-642-39286-3_7

Xiaocong He, Yongtao Li, and Lihua Feng. Extremal graphs for the odd prism. arXiv preprint, arXiv: 2302.03278, 2023.

Zhiyang He. A new upper bound on the Turán number of even cycles. Electron. J. Combin., 28(2):Paper No. 2.41, 18, 2021.
https://doi.org/10.37236/9861

Oliver Janzer. Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3. Int. Math. Res. Not. IMRN, 2022, to appear.
https://doi.org/10.1093/imrn/rnac076

János Kollár, Lajos Rónyai, and Tibor Szabó. Norm-graphs and bipartite Turán numbers. Combinatorica, 16(3):399-406, 1996.
https://doi.org/10.1007/BF01261323

Rom Pinchasi and Micha Sharir. On graphs that do not contain the cube and related problems. Combinatorica, 25(5):615-623, 2005.
https://doi.org/10.1007/s00493-005-0037-z

M. Simonovits. Extermal graph problems with symmetrical extremal graphs. Additional chromatic conditions. Discrete Math., 7:349-376, 1974.
https://doi.org/10.1016/0012-365X(74)90044-2

Miklós Simonovits. The extremal graph problem of the icosahedron. J. Combinatorial Theory Ser. B, 17:69-79, 1974.
https://doi.org/10.1016/0095-8956(74)90051-3

P. Turán. Eine extremalaufgabe aus der graphentheorie. Fiz Lapok, pages 436-452, 1941.

R. Wenger. Extremal graphs with no C4's, C6's, or C10's. J. Combin. Theory Ser. B, 52(1):113-116, 1991.
https://doi.org/10.1016/0095-8956(91)90097-4

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Jun Gao, Oliver Janzer, Hong Liu, Zixiang Xu

PDF