×

Independent sets in algebraic hypergraphs. (English) Zbl 1485.05120

Summary: In this paper we study hypergraphs definable in an algebraically closed field. Our goal is to show, in the spirit of the so-called transference principles in extremal combinatorics, that if a given algebraic hypergraph is “dense” in a certain sense, then a generic low-dimensional subset of its vertices induces a subhypergraph that is also “dense”. (For technical reasons, we only consider low-dimensional subsets that are parameterized by rational functions.) Our proof approach is inspired by the hypergraph containers method, developed by J. Balogh et al. [J. Am. Math. Soc. 28, No. 3, 669–709 (2015; Zbl 1310.05154)] and independently by D. Saxton and A. Thomason [Invent. Math. 201, No. 3, 925–992 (2015; Zbl 1320.05085)] (although adapting this method to the algebraic setting presents some unique challenges that do not occur when working with finite hypergraphs). Along the way, we establish a natural generalization of the classical dimension of fibers theorem in algebraic geometry, which is interesting in its own right.

MSC:

05C65 Hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
14A10 Varieties and morphisms
14A25 Elementary questions in algebraic geometry
05C35 Extremal problems in graph theory
05C63 Infinite graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Pach, J., Pinchasi, R., Radoičić, R., Sharir, M.: Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A 111, 310-326 (2005) Zbl 1099.14048 MR 2156215 · Zbl 1099.14048
[2] Balogh, J., Morris, R., Samotij, W.: Independent sets in hypergraphs. J. Amer. Math. Soc. 28, 669-709 (2015) Zbl 1310.05154 MR 3327533 · Zbl 1310.05154
[3] Balogh, J., Morris, R., Samotij, W.: The method of hypergraph containers. In: Proceedings of the International Congress of Mathematicians-Rio de Janeiro 2018. Vol. IV. Invited Lectures, World Scientific, Hackensack, 3059-3092 (2018) Zbl 1448.05147 MR 3966523 · Zbl 1448.05147
[4] Bernshteyn, A., Delcourt, M., Towsner, H., Tserunyan, A.: A short nonalgorithmic proof of the containers theorem for hypergraphs. Proc. Amer. Math. Soc. 147, 1739-1749 (2019) Zbl 07020584 MR 3910438 · Zbl 07020584
[5] Chernikov, A., Starchenko, S.: Regularity lemma for distal structures. J. Eur. Math. Soc. (JEMS) 20, 2437-2466 (2018) Zbl 06966829 MR 3852184 · Zbl 1459.03041
[6] Conlon, D.: Combinatorial theorems relative to a random set. In: Proceedings of the Interna-tional Congress of Mathematicians -Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, 303-327 (2014) Zbl 1373.05175 MR 3727614 · Zbl 1373.05175
[7] Conlon, D., Gowers, W. T.: Combinatorial theorems in sparse random sets. Ann. of Math. (2) 184, 367-454 (2016) Zbl 1351.05204 MR 3548529 · Zbl 1351.05204
[8] Ferber, A., McKinley, G., Samotij, W.: Supersaturated sparse graphs and hypergraphs. Int. Math. Res. Not. IMRN 2020, no. 2, 378-402 (2020) Zbl 1433.05152 MR 4073190 · Zbl 1433.05152
[9] Fox, J., Gromov, M., Lafforgue, V., Naor, A., Pach, J.: Overlap properties of geometric expanders. J. Reine Angew. Math. 671, 49-83 (2012) Zbl 1306.05171 MR 2983197 · Zbl 1306.05171
[10] Hrushovski, E.: Strongly minimal expansions of algebraically closed fields. Israel J. Math. 79, 129-151 (1992) Zbl 0773.12005 MR 1248909 · Zbl 0773.12005
[11] Johnson, W.: Fun with fields. Ph.D. thesis, University of California, Berkeley (2016) MR 3564042
[12] Kleitman, D. J., Winston, K. J.: On the number of graphs without 4-cycles. Discrete Math. 41, 167-172 (1982) Zbl 0491.05035 MR 676877 · Zbl 0491.05035
[13] Marker, D.: Model Theory. Grad. Texts in Math. 217, Springer, New York (2002) Zbl 1003.03034 MR 1924282 · Zbl 1003.03034
[14] Mumford, D.: The Red Book of Varieties and Schemes. Lecture Notes in Math. 1358, Springer, Berlin (1988) Zbl 0658.14001 MR 971985 · Zbl 0658.14001
[15] Pillay, A.: An Introduction to Stability Theory. Oxford Logic Guides 8, Oxford University, New York (1983) Zbl 0526.03014 MR 719195 · Zbl 0526.03014
[16] Sapozhenko, A.: Systems of containers and enumeration problems. In: Stochastic Algorithms: Foundations and Applications, Lecture Notes in Comput. Sci. 3777, Springer, Berlin, 1-13 (2005) Zbl 1159.68656 · Zbl 1159.68656
[17] Saxton, D., Thomason, A.: Hypergraph containers. Invent. Math. 201, 925-992 (2015) Zbl 1320.05085 MR 3385638 · Zbl 1320.05085
[18] Schacht, M.: Extremal results for random discrete structures. Ann. of Math. (2) 184, 333-365 (2016) Zbl 1351.05207 MR 3548528 · Zbl 1351.05207
[19] Suk, A.: Semi-algebraic Ramsey numbers. J. Combin. Theory Ser. B 116, 465-483 (2016) Zbl 1327.05331 MR 3425253 · Zbl 1327.05331
[20] Szemerédi, E.: On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27, 199-245 (1975) Zbl 0303.10056 MR 0369312 · Zbl 0303.10056
[21] Tao, T.: Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets. Contrib. Discrete Math. 10, 22-98 (2015) Zbl 1370.11135 MR 3386249 · Zbl 1370.11135
[22] Vakil, R.: The rising sea: foundations of algebraic geometry. httpsW//math.stanford.edu/ vakil/ 216blog/FOAGnov1817public.pdf (2017)
[23] Van den Dries, L. P. D.: Model theory of fields: Decidability, and bounds for polynomial ideals. Ph.D. thesis, Rijksuniversiteit Utrecht, Utrecht (1978)
[24] Van den Dries, L., Schmidt, K.: Bounds in the theory of polynomial rings over fields. A non-standard approach. Invent. Math. 76, 77-91 (1984) Zbl 0539.13011 MR 739626 · Zbl 0539.13011
[25] Varnavides, P.: On certain sets of positive density. J. Lond. Math. Soc. 34, 358-360 (1959) Zbl 0088.25702 MR 106865 · Zbl 0088.25702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.