Hostname: page-component-669899f699-qzcqf Total loading time: 0 Render date: 2025-04-30T01:20:19.822Z Has data issue: false hasContentIssue false
  • English
  • Français

Hypergraph removal with polynomial bounds

Part of: Graph theory

Published online by Cambridge University Press:  28 April 2025

LIOR GISHBOLINER  and
ASAF SHAPIRA
LIOR GISHBOLINER
Affiliation:
Department of Mathematics, University of Toronto, Canada. e-mail: [email protected]
ASAF SHAPIRA
Affiliation:
School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a fixed k-uniform hypergraph F, the F-removal lemma states that every hypergraph with few copies of F can be made F-free by the removal of few edges. Unfortunately, for general F, the constants involved are given by incredibly fast-growing Ackermann-type functions. It is thus natural to ask for which F one can prove removal lemmas with polynomial bounds. One trivial case where such bounds can be obtained is when F is k-partite. Alon proved that when $k=2$ (i.e. when dealing with graphs), only bipartite graphs have a polynomial removal lemma. Kohayakawa, Nagle and Rödl conjectured in 2002 that Alon’s result can be extended to all $k\gt2$, namely, that the only $k$-graphs $F$ for which the hypergraph removal lemma has polynomial bounds are the trivial cases when F is k-partite. In this paper we prove this conjecture.

MSC classification

Primary: 05C35: Extremal problems
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , First View , pp. 1 - 10
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

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.)

Article purchase

Temporarily unavailable

Footnotes

†

During this work, LG was supported by SNSF grant 200021_196965.

‡

Supported in part by ISF Grant 1028/16, ERC Consolidator Grant 863438 and NSF-BSF Grant 20196.

References

Alon, N., Testing subgraphs in large graphs. Random Structures Algorithms 21 (2002), 359–370.CrossRefGoogle Scholar
Alon, N. and Shapira, A., Linear equations, arithmetic progressions and hypergraph property testing. Theory of Computing vol. 1 (2005), 177–216.CrossRefGoogle Scholar
Behrend, F. A., On sets of integers which contain no three terms in arithmetic progression. Proc. Natl. Acad. Sci. U.S.A. 32 (1946), 331–332.Google Scholar
Erdős, P., On extremal problems of graphs and generalized graphs. Israel J. Math. 2 (1964), 183–190.CrossRefGoogle Scholar
Erdős, P., Frankl, P. and Rödl, V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 (1986), 113–121.Google Scholar
Gishboliner, L. and Tomon, I., On 3-graphs with no four vertices spanning exactly two edges. Bull. London. Math. Soc. 54 (2022), 2117–2134.CrossRefGoogle Scholar
Goldreich, O., Introduction to Property Testing. (Cambridge University Press, 2017).CrossRefGoogle Scholar
Gowers, W. T., Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. of Math. 166 (2007), 897–946.CrossRefGoogle Scholar
Kohayakawa, Y., Nagle, B. and Rödl, V., Efficient testing of hypergraphs. Proc. of the International Colloquium on Automata, Languages and Programming (ICALP) 2002, 1017–1028.CrossRefGoogle Scholar
Kővári, T., Sós, V. and Turán, P., On a problem of K. Zarankiewicz. Colloq. Math. 3 (1954), 50–57.CrossRefGoogle Scholar
Nagle, B., Rödl, V. and Schacht, M., The counting lemma for regular k-uniform hypergraphs. Random Structures Algorithms 28 (2006), 113–179.CrossRefGoogle Scholar
Rödl, V., Quasi-randomness and the regularity method in hypergraphs. Proceedings of the International Congress of Mathematicians (ICM) 1 (2015), 571–599.Google Scholar
Rödl, V. and Skokan, J., Regularity lemma for k-uniform hypergraphs. Random Structures Algorithms 25 (2004), 1–42.CrossRefGoogle Scholar
Ruzsa, I. and Szemerédi, E., Triple systems with no six points carrying three triangles. In Combinatorics (Keszthely, 1976). Coll. Math. Soc. J. Bolyai 18, vol. II (1978), 939–945.Google Scholar
Szemerédi, E., On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.CrossRefGoogle Scholar
Szemerédi, E., Regular partitions of graphs, In: Proc. Colloque Inter. CNRS, 1978, 399–401.Google Scholar
Tao, T., A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113 (2006), 1257–1280.CrossRefGoogle Scholar