Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-17T06:16:04.907Z Has data issue: false hasContentIssue false
  • English
  • Français

An Extremal Graph Problem with a Transcendental Solution

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  26 June 2018

DHRUV MUBAYI  and
CAROLINE TERRY
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: [email protected])
CAROLINE TERRY
Affiliation:
Department of Mathematics, University of Maryland, College Park, MD 20742, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that the number of multigraphs with vertex set {1, . . ., n} such that every four vertices span at most nine edges is an2+o(n2) where a is transcendental (assuming Schanuel's conjecture from number theory). This is an easy consequence of the solution to a related problem about maximizing the product of the edge multiplicities in certain multigraphs, and appears to be the first explicit (somewhat natural) question in extremal graph theory whose solution is transcendental. These results may shed light on a question of Razborov, who asked whether there are conjectures or theorems in extremal combinatorics which cannot be proved by a certain class of finite methods that include Cauchy–Schwarz arguments.

Our proof involves a novel application of Zykov symmetrization applied to multigraphs, a rather technical progressive induction, and a straightforward use of hypergraph containers.

MSC classification

Primary: 05D99: None of the above, but in this section
Secondary: 05C35: Extremal problems 05C22: Signed and weighted graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 2 , March 2019 , pp. 303 - 324
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research supported in part by NSF grant DMS 1300138.

References

[1] Alon, N. (2016) Personal communication.Google Scholar
[2] Balogh, J., Morris, R. and Samotij, W. (2015) Independent sets in hypergraphs. J. Amer. Math. Soc. 28 669–709.Google Scholar
[3] Bondy, J. A. and Tuza, Z. (1997) A weighted generalization of Turán's theorem. J. Graph Theory 25 267–275.Google Scholar
[4] Erdős, P., Kleitman, D. J. and Rothschild, B. L. (1976) Asymptotic enumeration of Kn-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie, Vol. II, Accad. Naz. Lincei, Rome, pp. 19–27.Google Scholar
[5] Erdős, P. and Simonovits, M. (1966) A limit theorem in graph theory. Studia Sci. Math. Hungar. 1 51–57.Google Scholar
[6] Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.Google Scholar
[7] Falgas-Ravry, V., O'Connell, K., Strömberg, J. and Uzzell, A. (2016) Multicolour containers and the entropy of decorated graph limits. arXiv:1607.08152Google Scholar
[8] Füredi, Z. and Kündgen, A. (2002) Turán problems for integer-weighted graphs. J. Graph Theory 40 195–225.Google Scholar
[9] Gelfond, A. (1934) Sur le septième problème de Hilbert. In Bulletin de l'Académie des Sciences de l'URSS: Classe des sciences mathématiques et naturelles, pp. 623–634.Google Scholar
[10] Grosu, C. (2016) On the algebraic and topological structure of the set of Turán densities. J. Combin. Theory Ser. B 118 137–185.Google Scholar
[11] Hatami, H. and Norine, S. (2011) Undecidability of linear inequalities in graph homomorphism densities. J. Amer. Math. Soc. 24 547–565.Google Scholar
[12] Lang, S. (1966) Introduction to Transcendental Numbers, Addison-Wesley.Google Scholar
[13] Mubayi, D. and Talbot, J. (2008) Extremal problems for t-partite and t-colorable hypergraphs. Electron. J. Combin. 15 R26.Google Scholar
[14] Mubayi, D. and Terry, C. (2015) Discrete metric spaces: Structure, enumeration, and 0–1 laws. J. Symbolic Logic, accepted. arXiv:1502.01212Google Scholar
[15] Mubayi, D. and Terry, C. (2016) An extremal graph problem with a transcendental solution. arXiv:1607.07742Google Scholar
[16] Mubayi, D. and Terry, C. (2016) Extremal theory of locally sparse multigraphs. arXiv:1608.08948Google Scholar
[17] Pikhurko, O. (2014) On possible Turán densities. Israel J. Math. 201 415–454.Google Scholar
[18] Razborov, A. (2007) Flag algebras. J. Symbolic Logic 72 1239–1282.Google Scholar
[19] Saxton, D. and Thomason, A. (2015) Hypergraph containers. Inventio. Math. 201 925–992.Google Scholar
[20] Terry, C. (2018) Structure and enumeration theorems for hereditary properties in finite relational languages. Ann. Pure Appl. Logic 169 413–449.Google Scholar
[21] Waldschmidt, M. (2014) Schanuel's conjecture: algebraic independence of transcendental numbers. In Colloquium De Giorgi 2013 and 2014, Vol. 5 of Colloquia, Ed. Norm., Pisa, pp. 129–137.Google Scholar