Extremal problems on hypergraphs and set families

Luo, Haoran

Permalink

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

Description

Title

Extremal problems on hypergraphs and set families

Author(s)

Luo, Haoran

Issue Date

2025-04-18

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, József

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Ford, Kevin
• Bradshaw, Peter

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2025-05

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Haoran Luo

Owning Collections