Dmitrii Zakharov

Hi, I'm a fifth year graduate student at MIT under the supervision of Larry Guth.
I'm interested in various topics in exremal and additive combinatorics, discrete geometry, geometric measure theory and harmonic analysis.

Email: zahkdm at mit dot edu.

CV: link (last update: 9/3/26)

Publications and preprints

List of all my papers with brief descriptions/comments. For a raw chronological list, see my CV.

Heilbronn's triangle problem

A new upper bound for the Heilbronn triangle problem (2023+), with A. Cohen and C. Pohoata

We showed that the smallest area of a triangle among $N$ points satisfies $\Delta < N^{-8/7-c}$ for some $c>0$, improving the 40 year old record by Komlos, Pintz and Szemeredi. Proof uses a recent development in geometric measure theory - a sharp radial projections theorem of Orponen-Shmerkin-Wang.

Lower bounds for incidences, Inventiones Mathematicae (2025) with A. Cohen and C. Pohoata

The minimal distance problem is the following question. Consider a collection of $N$ points in $[0,1]^2$ and draw a line through each point. Measure the distance between every point and a line through a different point. What is the smallest distance $\delta$ you are guaranteed to find? We prove that $\delta < N^{-2/3 +o(1)}$. As a corollary, we find triangles of area at most $N^{-7/6+o(1)}$, improving our previous bound. In some sense, this is the limit of the approach.

A fractal-like configuration of point-line pairs for the minimal distance problem (2025+) with A. Logunov

We give a construction showing that the answer to the minimal distance problem is at least $\delta > N^{-1+c}$ for some $c>0$. We start with a random example and then turn it into a self-affine fractal.
Hunter-Verstraete-Pohoata-Zhang gave a completely different construction based on a connection to the Furstenberg-Sarkozy problem about sets avoiding square differences. A high-degree version of this construction lead to $\delta > N^{-2/3+o(1)}$, matching our earlier upper bound.

Upper bounds for Heilbronn's triangle problem in higher dimensions, Bulletin of the London Mathematical Society (2024)

There are many extensions of Heilbronn's triangle problem: instead of triangles in the plane, look for other shapes in other dimensions. For example, among any $N$ points in $[0,1]^d$ there is a $d$-simplex of volume at most $N^{-\log d +C}$.

Heilbronn's triangle problem in three dimensions (2025+) with D. Maldague and H. Wang

We prove that $N$ points in $[0,1]^3$ determine a triangle of area at most $N^{-2/3-c}$ for some $c>0$. This gives the first improvement for Heilbronn's triangle problem in ${\mathbb R}^3$. To do so, we develop two refinements of Roth's high-low method based on two-ends and hairbrush arguments.

Small triangles, Journal of the London Mathematical Society (2026)

A survey for the centennial issue of the Journal of the London Mathematical Society.

Discrete geometry

The Erdos distinct distances problem in $\mathbb R^3$ (2026+) with J. Tidor and H-H. H. Yu

Consider a set of $N$ points in $\mathbb R^d$. What's the smallest number of distances they can determine? In the plane, Guth and Katz famously showed that the answer is $N^{1-o(1)}$. We prove that in 3D, the answer is $N^{2/3-o(1)}$.

Convex polytopes from fewer points, Duke (2025) with C. Pohoata

Consider a set of $N$ points in $\mathbb R^d$ in general position. What is the largest subset in convex position you can always find? In the plane, this is the classical Erdos-Szekeres problem and the answer is known to be $(1+o(1)) \log_2 N$. We prove that in dimensions $d\ge 3$ you can always find $\omega(\log N)$ points in convex position, i.e. significantly more than in the plane.

Spherical sets avoiding orthonormal bases, Comptes Rendus Mathematique (2025)

I prove that if $A \subset S^{n-1}$ is a subset of density at least $1 - 10^{-100}$ then it contains an orthonormal basis. The density threshold cannot be replaced by a number smaller than $0.68$.

Cutting corners, Journal of Combinatorial Theory, Series B (2025) with A. Kupavskii and A. Sagdeev

How dense can a subset of $\mathbb R^d$ be if it avoids unit $k$-dimensional simplices? We show that this density is less than $c^{n/k}$, $c<1$. We also give a simple proof of Frankl-Rodl theorem (using Frankl-Wilson as black-box).

Acute sets, Discrete and Computational Geometry (2019)

A subset in $\mathbb R^d$ is called acute if all angles in it are less than $90^\circ$. I construct an acute set of size $1.618^d$.
Later, Gerencser-Harangi constructed an example of size $2^{d-1}+1$ which is within a factor of 2 from optimal.

The right acute angles problem? European Journal of Combinatorics (2020) with A. Kupavskii

Now say we want a subset in $\mathbb R^d$ in which all angles are less than $90^\circ -\varepsilon $, for some small but fixed $\varepsilon>0$. Is there such a set of size $1.99^d$? We give an example of size $1.41^d$ and prove that it cannot be larger than $(2-\varepsilon^2)^d$.

Additive combinatorics

Moderate-doubling sets in $\mathbb F_2^n$ intersect subspaces (2025+) with A. Cohen

Let $A$ be a subset in some abelian group $G$ such that $|A+A| < |A|^{1.99}$. What can you say about the structure of $A$? For $G=\mathbb F_2^n$ we prove that $A$ must interact non-trivially with a subspace of dimension $ O( \log |A|)$.

Sharp bound for the Erdos-Straus non-averaging set problem, GAFA (2025) with H.T. Pham

Let $A \subset \{1, \ldots, N\}$ be a set such that no element of $A$ is an average of other elements of $A$. We prove that $A$ has size at most $N^{1/4+o(1)}$ and this is sharp.

Convex geometry and the Erdos-Ginzburg-Ziv problem, Discrete Analysis (2026)

Suppose that $A \subset \mathbb F_p^n$ is such that no $p$ elements of $A$ sum up to zero. How large can $A$ be? I prove that in the regime when $d$ is fixed and $p$ is large, $|A| \le 4^d p$. Furthermore, I characterize maximum size examples in terms of certain convex geometric structure. The key new idea is to use (a generalization of) the integer Helly theorem.

On the Erdos-Ginzburg-Ziv Problem in large dimension, accepted to AJM (2023+) with L. Sauermann

In the setup above, consider the opposite regime when $p$ is fixed and $d$ is large. We prove that $|A| \lesssim_{p,\varepsilon} (C_\varepsilon p^{\varepsilon})^d $ holds for any $\varepsilon>0$.

Zero subsums in vector spaces over finite fields, Algebra & Number Theory (2022) with C. Pohoata

Let $A \subset \mathbb F_p^d$ be such that no non-empty subset of $A$ has zero sum. We show that $|A| \le (d-1+o(1))p$ for every fixed $d$ and this is sharp.

Ruzsa's problem on Bi-Sidon sets, Combinatorica (2025) with J. Pach

A subset $A$ in $\mathbb Z$ is Sidon if it contains no non-trivial solutions to $a+b=c+d$. It is multiplicative Sidon if it has no non-trivial solutions to $ab=cd$. It is Bi-Sidon if it is both Sidon and multiplicative Sidon. We show that any set of size $N$ contains a bi-Sidon subset of size $N^{\frac13+\frac7{78}+o(1)}$, improving the 'easy' lower bound $N^{1/3}$.

Most integers are not a sum of two palindromes, Cambridge Phil. Soc. Math. Proc. (2024)

I prove that most interegers between $1$ and $N$ cannot be written as a sum of two palindromes. This was Problem 95 on Green's list of open problems.

An explicit economical additive basis, Combinatorics, Probability and Computing (2025) with V. Jain, H.T. Pham and M. Sawhney

We give an explicit construction of a set $A \subset \mathbb Z$ such that $A+A = \mathbb Z$ and every $N$ is represented in at most $N^{o(1)}$ ways. While the construction ended up being very simple, this was a $\$100$ Erdos question.

On skew corner-free sets with C. Pohoata

We construct a skew-corner free set in $[n]\times [n]$ of size $n^{5/4}$ disproving a conjecture of Kevin Pratt. Soon thereafter, a much stronger Behrend-type construction was found and corresponding upper bound obtained here and here.

Set systems

Spread approximations for forbidden intersections problems, Advances in Mathematics (2024) with A. Kupavskii

We introduce a new technique to study questions about set systems. The idea is to decompose the family into 'spread stars' and use Spread Lemma to understand how different stars interact. We give an application to $t$-intersecting and $t$-avoiding families of permutations. See here for a recent development of the method.

On the size of maximal intersecting families, Combinatorics, Probability and Computing (2024)

Suppose that $\mathcal F$ is a family of sets of size $n$ such that: 1) every two sets in $\mathcal F$ intersect and 2) $\mathcal F$ is inclusion-maximal with respect to this property. A classical Erdos-Lovasz encoding argument gives an estimate $|\mathcal F| \le n^n$. We improve this to $|\mathcal F| \le \exp( - n^{1/2-o(1)}) n^n$. We expect the answer to be $ (1/2+o(1))^n n^n$.

Regular bipartite graphs and intersecting families, Journal of Combinatorial Theory, Series A (2018) with A. Kupavskii

We give a new proof of the Hilton-Milner theorem (stability result for the Erdos-Ko-Rado theorem) and give some extensions. This project started at a summer school in Sochi in 2016: Andrey organized a project on set systems and gave Hilton-Milner as a difficult exercise on the problem sheet.

Sharp bounds for rainbow matchings in hypergraphs, Journal of the London Mathematical Society (2025) with C. Pohoata and L. Sauermann

Suppose we have a collection of $r$-uniform matchings each of size $t$. How many matchings are needed to find a new 'rainbow' matching of size $t$, i.e. one using at most one edge from each of the matchings? We give nearly sharp bounds for this question.

Uniform Set Systems with Uniform Witnesses with T-W. Chao and Z. Xu

Suppose that $\mathcal F$ is a $k$-uniform family in $\{1, \ldots, n\}$ with the following property: for every $F\in \mathcal F$ there is a $s$-subset $B_F \subset F$ that cannot be obtained by intersecting $F$ with another set $F'\in\mathcal F$. We give sharp bound on the size of such $\mathcal F$ for $s\le d/2$ and large $n$. For $s>d/2$, the problem behaves very differently.

Turan problems and other extremal combinatorics

Essentially tight bounds for rainbow cycles in proper edge-colourings, Proceedings of the London Mathematical Society (2025) with N. Alon, M. Bucic, L. Sauermann and O. Zamir

Suppose $G$ is a properly edge-colored graph on $N$ vertices. If the average degree of $G$ is at least $C\log N \log \log N$ then $G$ contains a rainbow cycle. This is sharp up to the $\log \log N$ factor.

The Extremal Number of Surfaces, International Mathematics Research Notices (2021) with A. Kupavskii, A. Polyanskii, I. Tomon

For every $g$ we show that a 3-uniform hypergraph with $C_g N^{5/2}$ edges contains a triangulation of a genus $g$ surface. This was extended to non-orientable surfaces here.

Random multilinear maps and the Erdos box problem, Discrete Analysis (2022) with D. Conlon and C. Pohoata

We give a constrution of a subset $A \subset \{1, \ldots, N\}^d$ that avoids all combinatorial $2\times \ldots \times 2$ subcubes. It improves the standard probabilistic bound for all $d$.

On the number of high-dimensional partitions, Proceedings of the London Mathematical Society (2024) with C. Pohoata

We give an estimate on the number of anti-chains in the box $\{1, \ldots, N\}^d$ when $N$ is fixed and $d$ large. A stronger bound was obtained here.

On the minimal period of integer tilings, Bulletin of the London Mathematical Society (2025) with I. Laba

Let $T \subset \mathbb Z$ be a set that tiles integers by translations. We show that then $T$ tiles integers by a set of translates with period $\exp(C \log^2 D / \log \log D)$ where $D = \operatorname{diam}(T)$.

Color avoidance for monotone paths, Discrete Analysis (2025) with E. Mulrenin and C. Pohoata

Color the set of all triples in $\{1, \ldots, N\}$ in red, blue and green. We prove that then there exists a monotone path of length $N^{1/9}$ that uses only two of the colors.

A sharp Ramsey theorem for ordered hypergraph matchings, Advances in Combinatorics (2025) with L. Sauermann

An ordered matching is a collection of pairwise disjoint sets on a linearly ordered ground set. Given a large ordered matching, there always is a large structured submatching. We prove a sharp quantitative version of this.

Asymptotically sharp bounds for affine subspace statistics in $\mathbb F_2^n$ (2026+) with T-W Chao and Z. Xu

Let $A\subset \mathbb F_2^n$ and sample a random affine $d$-space. How large can be the probability that the subspace intersects $A$ in exactly $s$ elements? We prove some estimates of this probability that are sharp for some ranges of parameters.

An isoperimetric inequality for word overlap (2026+)

Two words overlap if the suffix of the first is a prefix of the second. This paper gives a sharp bound on the product of densities of two sets without overlapping words.

Norm hypergraphs (2022+) with C. Pohoata

Norm graphs give explicit examples of graphs avoiding copies of complete bipartite subgraphs $K_{s,t}$. We generalize this construction to hypergraphs.

On the trifference problem for linear codes, IEEE Trans. on Information Theory (2022) with C. Pohoata

We study linear trifferent codes. The main bound in this paper was superseded by this.

Turan-type results for intersection graphs of boxes, Combinatorics, Probability and Computing (2020) with I. Tomon

Projection theory, harmonic analysis etc

Estimating the number of real zeros of linear combinations of radicals of polynomials (2026+) with G. Binyamini, A. Kiro, A. Logunov, D. Novikov.

A Continuum Beck-type Theorem for Hyperplanes (2025+) with P. Bright and A. Ortiz

Proves that a set in $\mathbb R^d$ of given Hausdorff dimension defines the 'right' amount of hyperplanes given that it satisfies a geometric non-concentration condition.

On sets of orthogonal exponentials on the disk (2024)

Gives a refinement of Iosevich-Kolountzakis bound by using Marstrand's slicing theorem.

Generalized Arithmetic Kakeya (2024+) with C. Pohoata

Proves an equivalence between two entropic formulations of the arithmetic Kakeya problem.

Graph coloring problems

Chromatic numbers of Kneser-type graphs, Journal of Combinatorial Theory, Series A (2020)

Chromatic Numbers of Some Distance Graphs, Mathematical Notes (2020)

Clique-chromatic numbers of graphs of intersections, Mathematical Notes (2019) with A. Raigorodskii

(note: no AI tools have been used in the creation of this page)