Ting-Wei Chao

A set of points $N\subseteq \mathbb{F}_q^d$ is a Nikodym set if, for any $x\in \mathbb{F}_q^d$, there is a line $\ell$ through $x$ such that $\ell\setminus\{x\}\subseteq N$. We conjecture that $|N|=q^d-O_d(q^{d/(d-1)})$ and prove it under an extra algebraic assumption.

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.

A family of subsets $\mathcal{A}$ of an $n$-element set is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$, but the sizes of pairwise intersections are divisible by $\ell$. Berlekamp and Graver showed that when is a $\ell$ is a prime, the maximum size of an $\ell$-Oddtown is $n$. For composite moduli with $ω$ distinct prime factors, the argument of Szegedy gives an upper bound of $ωn-ω\log_2 n$ on the size of an $\ell$-Oddtown. We improve this to $ωn-(2ω+\varepsilon)\log_2 n$ for most $\ell$ and $n$ using a combination of linear algebraic and Fourier-analytic arguments.

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 Eccles, called the partial shadow problem. The problem asks to determine the maximum number of $r$-sets of vertices that contain at least $d$ edges in an $n$-edge $(d-1)$-uniform hypergraph. In our previous work, we obtained an asymptotically tight upper bound via its connection to the joints problem, a problem in incidence geometry. In a different direction, Friedgut and Kahn generalized the Kruskal--Katona theorem by determining the maximum number of copies of any fixed hypergraph in an $n$-edge hypergraph, up to a multiplicative factor. In this paper, using the connection to the joints problem again, we generalize our previous work to show an analogous partial shadow phenomenon for any hypergraph, generalizing Friedgut and Kahn's result. The key idea is to encode the graph-theoretic problem with new kinds of joints that we call hypergraph joints. Our main theorem is a generalization of the joints theorem that upper bounds the number of hypergraph joints, which the partial shadow phenomenon immediately follows from. In addition, with an appropriate notion of multiplicities, our theorem also generalizes a generalization of Hölder's inequality considered by Finner.

In this short note, we present a purely entropic proof that in a $3$-edge-colored simple graph with $R$ red edges, $G$ green edges, and $B$ blue edges, the number of rainbow triangles is at most $\sqrt{2RGB}$.