Improvements on Induced Subgraphs of Given Sizes

Abstract

Given integers m and f, let $S_n(m,f)$ be the set consisting of all integers e such that every n-vertex graph with e edges contains an m-vertex induced subgraph with f edges, and let $\sigma (m,f)=\limsup _{n\rightarrow \infty } |S_n(m,f)|/\left( {\begin{array}{c}n\\ 2\end{array}}\right) $. As a natural extension of an extremal problem of Erdős, this was investigated by Erdős, Füredi, Rothschild and Sós 20 years ago. Their main result indicates that integers in $S_n(m,f)$ are rare for most pairs (m, f), though they also found infinitely many pairs (m, f) whose $\sigma (m,f)$ is a fixed positive constant. Here we aim to provide some improvements on this study. Our first result shows that $\sigma (m,f)\le \frac{1}{2}$ holds for all but finitely many pairs (m, f) and the constant $\frac{1}{2}$ cannot be improved. This answers a question of Erdős et al. Our second result considers infinitely many pairs (m, f) of special forms, whose exact values of $\sigma (m,f)$ were conjectured by Erdős et al. We partially solve this conjecture (only leaving two open cases) by making progress on some constructions which are related to number theory. Our proofs are based on the research of Erdős et al. and involve different arguments in number theory. We also discuss some related problems.

Keywords

Extremal graph theory / induced subgraphs / analytic number theory / 05D99 / 05C99

References

[1] Brown, W.G., Erdős, P., Sós, V.T.: Some extremal problems on $r$-graphs. In: New Directions in the Theory of Graphs (Proceedings of the 3rd Ann Arbor Conference, Univ. Michigan, Academic Press. New York, 1973) pp. 53–63 (1971)

[2] Erdős, P.: Extremal problems in graph theory. In: Theory of Graphs and Its Applications (Proceedings of the Symposium Held in Smolenice, Publ. House Czechoslovak Acad. Sci. Prague, 1964), pp. 29–36 (1963)

[3] ErdősP, FürediZ, RothschildBL, SósVT. Induced subgraphs of given sizes, Paul Erdős memorial collection. Discrete Math., 1999, 200(1–3): 61-77.

[4] Füredi, Z., Simonovits, M.: The history of degenerate (bipartite) extremal graph problems. In: Erdős Centennial, pp. 169–264. Bolyai Society Mathematical Studies 25, János Bolyai Math. Soc., Budapest (2013)

[5] GreenhillC, IsaevM, KwanM, McKayBD. The average number of spanning trees in sparse graphs with given degrees. Eur. J. Comb., 2017, 63: 6-25.

[6] Heath-BrownDR. A new form of the circle method, and its application to quadratic forms. J. Reine Angew. Math., 1996, 481: 149-206

[7] Iwaniec, H., Kowalski, E.: Analytic Number Theory. Colloquium Publications 53 (2004)

[8] LeVequeWJFundamentals of Number Theory, 1996, North Chelmsford. Courier Corporation.

[9] RothKF. On certain sets of integers. J. Lond. Math. Soc., 1953, 28: 104-109.

[10] Ruzsa, I.Z., Szemerédi, E.: Triple systems with no six points carrying three triangles. In: Combinatorics (Proceedings of the Fifth Hungarian Colloquium, Keszthely, Vol. II, Colloquia Mathematica Societatis Janos Bolyai, vol. 18. North-Holland, Amsterdam, 1978), pp. 939–945 (1976)

[11] VaughanRCThe Hardy–Littlewood Method, 20092Cambridge. Cambridge University Press.

Funding

The National Key R and D Program of China(2020YFA0713100)

China National Funds for Distinguished Young Scientists(12125106)

National Natural Science Foundation of China(11922113)

Innovation Program for Quantum Science and Technology(2021ZD0302904)

Anhui Initiative in Quantum Information Technologies grant(AHY150200)

RIGHTS & PERMISSIONS

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature