Sharp density bounds on the finite field Kakeya

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

Extremal graphs without exponentially-small bicliques

The Turan problem asks for the largest number of edges in an $n$-vertex graph not containing a fixed forbidden subgraph $F$. We construct a new family of graphs not containing $K_{s,t}$, for $t= C^s$, with $Omega(n^{2-1/s})$ edges matching the upper bound of Kovari, Sos and Turan.

Digital almost nets

Digital nets (in base $2$) are the subsets of $[0,1]^d$ that contain the expected number of points in every not-too-small dyadic box. We construct sets that contain almost the expected number of points in every such box, but which are exponentially smaller than the digital nets. We also establish a lower bound on the size of such almost nets.

Longest common subsequences between words of very unequal length

We consider the expected length of the longest common subsequence between two random words of lengths $n$ and $(1-varepsilon)kn$ over $k$-symbol alphabet. It is well-known that this quantity is asymptotic to $gamma_{k,varepsilon} n$ for some constant $gamma_{k,varepsilon}$. We show that $gamma_{k,varepsilon}$ is of the order $1-cvarepsilon^2$ uniformly in $k$ and $varepsilon$. In addition, for large $k$, we give evidence that $gamma_{k,varepsilon}$ approaches $1-tfrac{1}{4}varepsilon^2$, and prove a matching lower bound.

Empty axis-parallel boxes

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 $Omega(d/n)$ as $ntoinfty$ and $d$ is fixed. In the opposite direction, we give a construction without an empty axis-parallel box of volume $O(d^2log d/n)$. These improve on the previous best bounds of $Omega(log d/n)$ and $O(2^{7d}/n)$ respectively.

On convex holes in $d$-dimensional point sets

Given a finite set $A subseteq mathbb{R}^d$, points $a_1,a_2,dotsc,a_{ell} in A$ form an $ell$-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 $mathbb{R}^d$ having no holes of size $O(4^ddlog d)$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. The basic version of our construction uses a certain type of equidistributed point sets, originating from numerical analysis, known as $(t,m,s)$-nets or $(t,s)$-sequences, yielding a bound of $2^{7d}$. The better bound is obtained using a variant of $(t,m,s)$-nets, obeying a relaxed equidistribution condition.

Order-isomorphic twins in permutations

Let $a_1,dotsc,a_n$ be a permutation of $[n]$. Two disjoint order-isomorphic subsequences are called emph{twins}. We show that every permutation of $[n]$ contains twins of length $Omega(n^{3/5})$ improving the trivial bound of $Omega(n^{1/2})$. We also show that a random permutation contains twins of length $Omega(n^{2/3})$, which is sharp.

Periodic words, common subsequences and frogs

Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. We show several results about the length of the longest common subsequence (LCS) between $W^{(n)}$ and $R_n$; in particular, we show that its expectation is $gamma_W n-O(sqrt{n})$ for an efficiently-computable constant $gamma_W$. This is done by relating the problem to a new interacting particle system, which we dub frog dynamics. In this system, the particles (`frogs) hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushTASEP. In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics. In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS.

Linear orderings of combinatorial cubes

We show that, for every linear ordering of $[2]^n$, there is a large subcube on which the ordering is lexicographic. We use this to deduce that every long sequence contains a long monotone subsequence supported on an affine cube. More generally, we prove an analogous result for linear orderings of $[k]^n$. We show that, for every such ordering, there is a large subcube on which the ordering agrees with one of approximately $frac{(k-1)!}{2(ln 2)^k}$ orderings.

Turan numbers of theta graphs

The theta graph $Theta_{ell,t}$ consists of two vertices joined by $t$ vertex-disjoint paths of length $ell$ each. For fixed odd $ell$ and large $t$, we show that the largest graph not containing $Theta_{ell,t}$ has at most $c_{ell} t^{1-1/ell}n^{1+1/ell}$ edges and that this is tight apart from the value of $c_{ell}$.