Ting-Wei Chao

On Colorful Kruskal--Katona Theorems

Ting-Wei Chao, Maya Sankar, Hung-Hsun Hans Yu

What is the maximum number of rainbow triangles in an edge-colored graph with $m$ edges and $r$ colors? Using entropic techniques, we prove an upper bound of $C_{r} m^{3/2}$ rainbow t…

Asymptotics of the Brown--Erdős--Sós problem at integer exponents

Ting-Wei Chao, Xinqi Huang, Hong Liu

The Brown--Erdős--Sós problem is a fundamental problem in sparse hypergraph Turán theory. For integers $r, k \geq 2$ and $s \geq r$ , the problem asks for the maximum number $f^{(r)}(n;s…

Asymptotically sharp bounds for affine subspace statistics in $F_{2}^{n}$

Ting-Wei Chao, Zixuan Xu, Dmitrii Zakharov

Given a subset $A \subseteq F_{2}^{n}$ , we can consider the distribution of the intersection size of $A$ with a uniformly random $d$ -flat $F$ . Motivated by the edge statistics…

A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes

Ting-Wei Chao, Zichao Dong, Hong Liu +2

We study the Zarankiewicz problem for $r$ -partite, $r$ -uniform intersection hypergraphs arising from $r$ families of axis-parallel boxes in $R^{d}$ with prescribed direction…

Uniform Set Systems with Uniform Witnesses

Ting-Wei Chao, Zixuan Xu, Dmitrii Zakharov

Frankl--Pach and Erdős conjectured that any $(d + 1)$ -uniform set family $F \subseteq (d + 1 [ n ])$ with VC-dimension at most $d$ has size at most $(d n - 1)$ when…

Vertex-minor universality of a random graph

Ting-Wei Chao, Zixuan Xu

Given a graph $G$ and a vertex $v \in V (G)$ , a local complementation at $v$ on $G$ is an operation that replaces the induced graph on the neighborhood of $v$ by its complement. A gr…

Finite field Nikodym problem for spread line sets

Ting-Wei Chao, Hung-Hsun Hans Yu

A set of points $N \subseteq F_{q}^{d}$ is a Nikodym set if, for any $x \in F_{q}^{d}$ , there is a line $ℓ$ through $x$ such that $ℓ ∖ {x} \subseteq N$ . We con…

Edge inducibility via local directed graphs

Ting-Wei Chao, Asaf Cohen Antonir, Anqi Li +1

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 Pip…

The Oddtown problem modulo a composite number

Boris Bukh, Ting-Wei Chao, Zeyu Zheng

A family of subsets $A$ of an $n$ -element set is called an $ℓ$ -Oddtown if the sizes of all sets are not divisible by $ℓ$ , but the sizes of pairwise intersections ar…

Even-degeneracy of a random graph

Ting-Wei Chao, Dingding Dong, Zixuan Xu

A graph is even-degenerate if one can iteratively remove a vertex of even degree at each step until at most one edge remains. Recently, Janzer and Yip showed that the Erdős--Renyi…

Uniform set systems with small VC-dimension

Ting-Wei Chao, Zixiang Xu, Chi Hoi Yip +1

We investigate the longstanding problem of determining the maximum size of a $(d + 1)$ -uniform set system with VC-dimension at most $d$ . Since the seminal 1984 work of Frankl and Pac…

When entropy meets Turán: new proofs and hypergraph Turán results

Ting-Wei Chao, Hung-Hsun Hans Yu

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…

Many cliques with small degree powers

Ting-Wei Chao, Zichao Dong, Zijun Shen +1

Suppose $0 < p \leq \infty$ . For a simple graph $G$ with a vertex-degree sequence $d_{1}, \dots, d_{n}$ satisfying $(d_{1}^{p} + \dots + d_{n}^{p})^{1/ p} \leq C$ , we prove asymptotically sharp u…

When Joints Meet Extremal Graph Theory: Hypergraph Joints

Ting-Wei Chao, Hung-Hsun Hans Yu

The Kruskal--Katona theorem determines the maximum number of $d$ -cliques in an $n$ -edge $(d - 1)$ -uniform hypergraph. A generalization of the theorem was proposed by Bollobás and Ecc…

Empty red-red-blue triangles

Ting-Wei Chao, Zichao Dong, Zhuo Wu

Let $P$ be a $2 n$ -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^{3/2})$ r…