My primary research interest lies in Combinatorics. I have been thinking about problems in discrete geometry more than other ones, but I am also interested in other areas of Combinatorics.
A joint in the three-dimensional space is a point lying on three lines that are not coplanar. The joints problem asks to determine the maximum number of joints given the number of lines. There are lots of extensions and variants of this problem.
In this paper, we encode an extremal-graph-theoretic problem using joints and give an alternative proof of Friedgut and Kahn's result, which determines the maximum number of copies of a fixed hypergraph H in any hypergraphs with N edges. This encoding allows us to improve Friedgut and Kahn's result for certain hypergraphs. Curiously, even though the improved statement is entirely graph-theoretic, our proof uses the polynomial method, and this is the only known proof.
In this paper, we prove that x choose (d-1) lines in a d-dimensional space determine at most x choose d joints. This is tight for integral x, and we also determine all the configurations meeting this upper bound.
Inspired by the joints problem, we consider several graph-theoretic problems where the number of edges is given and we are asked to determine the maximum number of vertex subsets with the desired induced structure. We focus on two particular instances of such settings: determining the maximum number of rainbow triangles given the numbers of red, green and blue edges, and the Kruskal--Katona theorem. We use the entropy method to show some strong bounds in both cases, and list some interesting open problems of the same flavor.
In the joints problem, we may consider a variant where lines are replaced with two-dimensional flats or even some other varieties in general. In this paper, we resolve the joints problem for varieties up to a multiplicative constant factor, and our result also generalizes all known variants of the joints problem.
See here for an online talk given by Yufei.
In this paper, we resolve the joints problem (for lines) up to an o(1)-factor. The main ingredient is a new vanishing lemma designed for the joints problem leading to an inequality with parameters that we may choose.
The polynomial method is useful not only for the joints problem but also for a wide variety of other problems. Applications of the polynomial method that are not related to the joints problem are listed here.
It is a central open problem in incidence geometry to characterize extremal configurations for the Szemerédi--Trotter theorem, which gives an essentially tight upper bound on the number of incidences between n points and m lines. In this paper, we make an initial progress toward such characterization, showing that the configuration is determined mostly by its incidence structure in some sense.
A semialgebraic hypergraph is a hypergraph where the set of edges can be described by some semialgebraic relations with low complexities. With a novel multilevel polynomial partitioning scheme, we obtain an optimal and oblivious regularity lemma, a best-known Turán-type result and a best-known Zarankiewicz-type result for semialgebraic hypergraphs.
I somehow wandered into the world of hypergraphs. For now, I am mostly working on hypergraph Ramsey problems and hypergraph Turán problems.
Erdős and Hajnal considered the following generalization of the off-diagonal Ramsey problem: given positive integers k, s, e and t, what is the minimum number N so that any red-blue coloring of the complete k-uniform hypergraph on n vertices contains either s vertices spanning at least e red edges, or a blue clique of size t. They conjectured that when k, s, e are fixed, the Ramsey number grows either polynomially or exponentially in t; and more strikingly, there is a sharp threshold for e (when k and s are fixed) when this jump from polynomial to exponential occurs. This conjecture was proven by Mubayi and Razborov recently for k at least four by a clever reduction to an inducibiility problem. In this paper, we prove the last remaining case k = 3 by reducing it to another Turán-type problem using "When are off-diagonal hypergraph Ramsey numbers polynomial" listed below.
Let k be a positive integer, and H be a linear k-uniform hypergraph. A folklore conjecture asserted that the off-diagonal Ramsey number r(H,N) grows polynomially in N, which was disproved by Conlon--Fox--Gunby--He--Mubayi--Suk--Verstraëte. In this paper, we furthermore show that for some linear hypergraph, the off-diagonal Ramsey number has a tower height close to the maximum possible by a stepping-up argument.
The classical Turán's theorem determines the maximum number of edges in a graph with no cliques on (r+1) vertices. In this paper, we give a new proof that can be rephrased using the entropy method. By extending our argument to hypergraphs, we also obtain some new hypergraph Turán results. An interesting side product is an entropic formulation of Lagrangian and spectral radius of a graph or a hypergraph.
Given a hypergraph, its off-diagonal Ramsey number is the smallest size of clique on which any red/blue coloring of the edges either gives a red copy of the hypergraph or a blue clique of size n. It is known that for 3-uniform hypergraphs that are "iterated tripartite", their off-diagonal Ramsey numbers are polynomial in n. In this paper, we prove the converse for hypergraphs with at most two tightly connected components.
This is a short note that gives an alternative (and better in some sense) proof of the rainbow triangle result in Kruskal--Katona-Type Problems via the Entropy Method.
A sock ordering is a sequence of socks with some colors, and a sock ordering is foot-sortable if it can be rearranged using a stack so that socks of the same color form a contiguous block. In this paper, I show how foot-sortability can be determined in O(N log N) time, and also classify all the minimal sock orderings with no colors appearing more than twice that are not foot-sortable.