In this paper we introduce the edge inducibility problem. This is a common refinement of both the well known Kruskal--Katona theorem and the inducibility question introduced by Pippenger and Golumbic.

Our first result is a hardness result. It shows that for any graph G, there is a related graph G' whose edge inducibility determines the vertex inducibility of G. Moreover, we determine the edge inducibility of every G with at most 4 vertices, and make some progress on the cases G=C_5, P_6. Lastly, we extend our hardness result to graphs with a perfect matching that is the unique fractional perfect matching. This is done by introducing locally directed graphs, which are natural generalizations of directed graphs

In this paper, we provide a new proof of a density version of Turán's theorem. We also rephrase both the theorem and the proof using entropy. With the entropic formulation, we show that some naturally defined entropic quantity is closely connected to other common quantities such as Lagrangian and spectral radius. In addition, we also determine the Turán density for a new family of hypergraphs, which we call tents. Our result can be seen as a new generalization of Mubayi's result on the extended cliques.

We study the maximum number of t-cliques in graphs with fixed p-norm of the degree sequence, i.e. (sum_v deg(v)^p)^{1/p} being fixed. When p<=t-1, the optimal is given by a large clique, and we have a transition when p exceed t-1, where the optimal becomes a union of several cliques of fixed sizes.

We revisited the proof of the rainbow triangle problem (T^2<= 2RGB), and provided a purely entropic proof. The key ingredient is a weird injection map out of nowhere.

Using the entropy method, we prove that, in a 3-colored graph with R red, G green, B blue edges, the number of rainbow triangles is at most (2RGB)^{1/2}, which is sharp. Also, we give a generalization of the Kruskal--Katona theorem that implies many other previous generalizations.

Gan, Loh, and Sudakov conjectured that the graph on n vertices with maximum degree at most ∆ that maximizing the number of t-cliques is a disjoint union of many ∆+1 cliques and a smaller clique. They also proved that the conjecture in true for all t>3 if it's true for t=3. Chase proved the case t=3. In this paper, we simplified and generalized the proof of Chase and give a unified proof for all t>=3.

A Kakeya set in F_q^n is a set containing a line in every direction. We show that every Kakeya set in F_q^n has density at least 1/2^{n−1}, matching the construction by Dvir, Kopparty, Saraf and Sudan.

A family of sets in [n] is called an l-Oddtown if the sizes of all sets are not divisible by l, but the sizes of pairwise intersections are divisible by l. We proved that the number of sets in any l-Oddtown is at most omega*n-(2omega+eps)log_2 n for most n,l, where omega is the number of prime factors of l.

Let F be a (d+1)-uniform set family. Assume that for each A in F, there is a subset B of A such that A\cap A'\neq B for any A' in F. What can we say about the size of F? It was conjectured that the optimal construction is a star, so the maximum may be (n-1 choose d). However, this is false, and there are constructions of size (n-1 choose d)+(n-4 choose d-2). Yet, the previous known upper bound was around (n choose d). In this paper, we show an upper bound (n-1 choose d)+O(n^{d-1-1/(4d-2)}).

Moreover, we suggested a modification of the conjecture that might be true: Instead of having a subset B of any size, we also require B to be uniform. That is, let 0<=s<=d. Assume that for each A in F, there is a subset B of A "of size s" such that A\cap A'\neq B for any A' in F. Is |F|<=(n-1 choose d)? If s=0, the conjecture becomes Erdős--Ko--Rado theorem. In this paper, we comfirm the conjecture for s=1,d.

Let P be a 2n-point set in the plane that is in general position. We prove that every red-blue bipartition of P into R and B with |R|=|B|=n generates Ω(n^{1.5}) red-red-blue empty triangles.

Update: the result has already appeared in https://arxiv.org/abs/2002.10646

Digital nets (in base 2) are the subsets of [0,1]^d that contain exactly the expected number of points in every not-too-small dyadic box. We construct finite sets, which we call "almost nets", such that every such dyadic box contains almost the expected number of points from the set, but whose size is exponentially smaller than the one of nets. We also establish a lower bound on the size of such almost nets.

We show that, for every set of n points in the d-dimensional unit cube, there is an empty axis-parallel box of volume at least Ω(d/n) as n→∞ and d is fixed. In the opposite direction, we give a construction without an empty axis-parallel box of volume O(d^2*log d/n)⁠. 

Given a finite set A of points in R^d, we say that points a_1,a_2,…,a_k in A form an k-hole in A if they are the vertices of a convex polytope, which contains no points of A in its interior. We construct arbitrarily large point sets in general position in  R^d having no holes of size O(4^d*d*log d) or more.

A graph is even-degenerate if one can iteratively remove a vertex of even degree at each step until at most one edge remains. In this paper, we show that for any constant 0<p<1, the random graph G(n,p) is even-degenerate with high probability.

In this paper we present an improved asymptotic normality criterion, along with several variant versions, which usually just ask for one coefficient of the generating function, without knowing any roots. In virtue of these new criteria, the asymptotic normality of some usual combinatorial statistics can be revealed and extended. Among which, we introduce the applications to matching numbers and Laplacian coefficients in detail.

In this paper, we provide a bijective proof that the ascent number over k-inversion sequences of length n is equidistributed with a weighted variant of the ascent number of permutations of order n.