Extremal problems on hypergraphs and set families

Extremal Combinatorics is one of the main branches of modern Combinatorics. Generally speaking, it deals with the problems about the extremal size of discrete structures given that they satisfy certain assumptions. These problems have inspired enormous new techniques in recent decades and have a large number of surprising connections with other fields of mathematics. This dissertation consists of several results in this area. Our first topic is about Turán problems, which is a central, extensively studied topic in Extremal Combinatorics. In the classical setting, it studies the problems about the maximum number of edges a (hyper)graph can have without containing a given (hyper)graph as a subgraph. Thanks to the previous results by Erdős, Stone, and Simonovitz, we have a reasonable understanding of these problems for graphs, while for hypergraphs, these problems become notoriously difficult even for the simplest case where the uniformity is three. A natural class of hypergraphs to consider for this problem is the tight cycles and the hypergraphs obtained from tight cycles by removing some edges. In Chapter 2, together with Balogh, we determine the maximum possible edge density of three-uniform hypergraphs without containing a long enough tight cycle minus one edge. As a direct corollary of this result, we give a human checkable answer to the question by Bárány and Füredi about the maximum number of triangles formed by n points in the plane in which every angle differs from a given value by at most a small fixed value. In Chapter 3, together with Balogh and Jiang, we study some generalized Turán problems about the maximum number of cliques of size r in a graph without containing a fixed complete r partite subgraph. We improve the upper bounds implied by the corresponding hypergraph Turán problems and also give several lower bound constructions. The second topic is concerned with the extremal problems in Discrete Geometry. In an affine space of dimension d, a set of points is said to be in general position if no d + 1 points in this set are contained in a (d − 1) dimensional affine subspace. This notion is closely related to many central problems in Discrete Geometry. Roche-Newton and Warren initiated the study of the following problem: What is the maximum possible size of a point set in general position in a random subset of an affine space over a finite field? In Chapter 4, together with Balogh, we answer this problem for 3-dimensional cases, by providing a balanced supersaturation result on the number of the sets of 4-points in the same plane. The last topic is about the extremal set theory, which asks about how many sets we can have given that they satisfy certain requirements. A very natural requirement of a set family is that the sets in it intersect in a given way. For example, the celebrated Erdős–Ko–Rado theorem gives the tight upper bound for a set family in which every pair of sets has a non empty intersection. We say a set family is maximal k-wise intersecting if the intersection of every collection of at most k sets in it is non-empty, and no extra set can be added to it while preserving this property. An old question by Erdős and Kleitman from 1974 asks for the smallest size of a maximal k-wise intersecting family on a ground set of size n. In Chapter 5, together with Balogh, Chen, Hendrey, Lund, Tompkins, and Tran, we answer this question for the case k = 3 and sufficiently large n by characterizing the extremal constructions. We also improve the lower bounds for the cases k ⩾ 4.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Luo, Haoran

Contributors dc:contributor

• Balogh, József
• Kostochka, Alexandr
• Ford, Kevin
• Bradshaw, Peter

• Extremal Combinatorics
• Turán's theorem
• Discrete Geometry
• Extremal Set Theorey

Statement dc:rights

• Copyright 2025 Haoran Luo

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129403

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129403