| Title | Summary | Download |
| “Maximum pebbling number of graphs of diameter three” | Pebbling number of a graph of diameter 3 on n vertices is no more than 3n/2+O(1), and the bound is sharp. Appeared in J. of Graph Theory, vol. 52(4), pp. 353–357, 2006.
| pdf ps |
| “A point in many triangles” | For every finite set of points in the plane we can find a point which lies in 2/9 of all the triangles formed by the points of this set. Appeared in Electronic J. of Combinatorics, vol. 13, N10, 2006.
| pdf ps html |
| “Induced subgraphs of Ramsey graphs with many distinct degrees” (with Benny Sudakov) | A graph with no clique or independent set of size Clog n contains an induced subgraph in which β(C)√n vertices have different degrees. Appeared in J. Combinatorial Theory Ser. B, vol. 97, pp. 612–619, 2007.
| pdf ps |
| “Measurable sets with excluded distances” | The density of any set in the plane in which the distances d1,...,dk do not occur is exponentially small in k provided the ratios d2/d1,...,dk/dk-1 tend to infinity. Appeared in Geom. and Funct. Analysis, vol. 18(3), pp. 668–697, 2008.
| pdf talk |
| “Non-trivial solutions to a linear equation in integers” | For k≥3 every set A⊆[1,N] not containing a solution to a1x1+⋯+akxk=a1xk+1+⋯+akx2k in distinct integers has O(N1/2−ε) elements for some ε>0 depending on the coefficients of the equation. Appeared in Acta Arithmetica, vol. 131(1), pp. 51–55, 2008.
| pdf ps |
| “Discrete Kakeya-type problems and small bases” (with Noga Alon and Benny Sudakov) | For many groups G there are constructions of small subsets of G that contain a translate of every k-element set. The constructions are used to exhibit efficient additive bases for subsets of integers. Appeared in Israel Journal of Mathematics, vol. 174, pp. 285–301, 2009.
| pdf ps |
| “Sums of dilates” | For any finite set of integers A the sumset A+100⋅A has at least 101|A|−o(|A|) elements, where 100⋅A={100 a : a∈A} is the 100-dilate of A. The bound is sharp. If |A+A|≤K|A|, then |A+100⋅A|≤K22|A|. Plünnecke's inequality yields only |A+100⋅A|≤K101|A|. Appeared in Combin. Probab. Comput., vol. 17, pp. 627–639, 2008.
| pdf ps talk |
| “Set families with a forbidden subposet” | The asymptotically largest subset of the Boolean lattice not containing a given subposet is a union of several middle levels of the Boolean lattice. While likely being true in general, this is proved only if the Hasse diagram of the forbidden subposet is a tree. Appeared in Electronic J. of Combinatorics, vol. 16, R142, 2009.
| pdf ps talk errata |
| “Stabbing simplices by points and flats” (with Jiří Matoušek and Gabriel Nivasch) | There is an n-point set S in Rd such that no p in Rd is contained in more than (n/(d+1))d+1 simplices spanned by S. In the opposite direction, for every S there is a (d−2)-dimensional affine subspace of Rd that intersects many triangles spanned by S. Appeared in Discrete Comput. Geom., vol. 43, pp. 321–338, 2010.
| pdf ps talk |
| “Lower bounds for weak epsilon-nets and stair-convexity” (with Jiří Matoušek and Gabriel Nivasch) | There are sets S in Rd which admit no weak (1/r)-net of size less than cd r logd−1r, where a set N is a weak ε-net for S if N meets every convex set C with |C∩S|≥ε|S|. Appeared in Israel Journal of Mathematics, vol. 182, pp. 199–228, 2011.
Preliminary version appeared in SoCG'09. | pdf talk |
| “Sum-product estimates for rational functions” (with Jacob Tsimerman) | For a set A⊆Fp and a polynomial f(x,y), the image f(A,A) is a much larger set than A unless f encodes a group operation. While surely true for arbitrary f and A, this is proved only if f is monic and A is large. For every f and A the estimate |f(A)+f(A)|+|AA|≥|A|1+ε is also proved. Appeared in Proc. of the London Math. Soc., vol. 104(1), pp. 1–26, 2012.
| pdf ps extra talk |
| “Multidimensional Kruskal–Katona theorem” | A shadow of a d‑tuple of sets consists of all the d‑tuples of sets that are obtained by removing an element from each set in the tuple. We give an essentially sharp lower bound on the size of such shadows. Appeared in SIAM J. Discrete Math., vol. 26(2), pp. 548–554, 2012.
| pdf ps errata |
| “Radon partitions in convexity spaces” | Tverberg's theorem asserts that any (k−1)(d+1)+1 points in Rd can be partitioned into k parts whose convex hulls meet. We show that the case k=2 does not combinatorially imply the full Tverberg's theorem. However, it does combinatorially imply a weakening of Tverberg's theorem. Accepted to Discrete Comput. Geom.
| pdf ps faq |
| “Space crossing numbers” (with Alfredo Hubard) | The crossing lemma says that in every drawing of a graph with n vertices and m≥4n edges in the plane there are at least cm3/n2 crossings. We define a notion of crossing for a drawing of a graph in R3, and show a lower bound for the number of such crossing that almost implies the crossing lemma. Appeared in Combin. Probab. Comput., vol. 21(3), pp. 358–373, 2012.
Preliminary version appeared in SoCG'11. | pdf ps talk |
| “Upper bounds for centerlines” (with Gabriel Nivasch) | For every n-point set S in R3 there is a line l such that every halfspace containing l contains at least 2n/5 points of S, and the fraction 2/5 is sharp. Appeared in J. Comput. Geom., vol. 3(1), 2012.
| |
| “Turán numbers for Ks,t-free graphs: topological obstructions and algebraic constructions” (with Pavle Blagojević and Roman Karasev) | For no s≥4 there is a construction of an extremal Ks,s-free graphs that comes from a hypersurface in Rs×Rs (but there is for s=2,3). There are constructions of hypersurfaces in Cs×Cs that give rise to extremal constructions for the Zarankiewicz problem when t≥s4s. Appeared in Israel Journal of Mathematics, vol. 197(1), pp. 199–214, 2013.
| pdf ps talk |
| “Erdős–Szekeres-type statements: Ramsey function and decidability in dimension 1” (with Jiří Matoušek) | Consider the generalization of Erdős–Szekeres theorem to any properties expressed by polynomial equations and inequalities, in any number of variables. In dimension 1, there is an algorithm that automatically decides a validity of such a theorem. The associated Ramsey function is at most doubly-exponential; in contrast, Ramsey's theorem yields a tower of exponents growing with the arity. Appeared in Duke Math. Journal, vol. 163(12), pp. 2243–2270, 2014.
| pdf extra |
| “Suborbits in Knaster's problem” (with Roman Karasev) | Bronisław Knaster asked to generalize the Borsuk–Ulam theorem from pairs to tuples of points. A natural approach is to embed the tuple into an orbit of a group action, and use Borsuk–Ulam-type result for the group. The approach succeeds in resolving Knaster's problem for non-equatorial triangles, but is proven to fail in general. An approximate version of Knaster's problem, which is motivated by Dvoretzky's theorem, is shown to require non-commutative groups. Appeared in Bulletin of the London Math. Soc., vol. 46(2), pp. 269–278, 2014.
| pdf ps |
| “An improvement of the Beck–Fiala theorem” | Beck and Fiala proved a bound on the discrepancy of a set system that depends only on the degree. We improve their bound by a tiny function going to infinity. Appeared in Combin. Probab. Comput., vol. 25(3), pp. 380–398, 2016.
| pdf ps |
| “Twins in words and long common subsequences in permutations” (with Lidong Zhou) | Every long sequence of symbols from a fixed alphabet contains two long identical disjoint subsequences ('twins'). Every large set of permutations contains two permutations having a long common subsequence. The problems of twins and permutations are quantitatively related. The relation is used to prove that every n-letter word over a k-letter alphabet contains twins of length Ω(k−2/3n). Appeared in Israel Journal of Mathematics, vol. 213, pp. 183–209, 2016.
| pdf ps code talk |
| “A bound on the number of edges in graphs without an even cycle” (with Zilin Jiang) | An easy upper bound on the number of edges in a graph without any cycles of length up to 2k is n1+1/k. If cycles of length only 2k are forbidden, the known upper bounds are of the form γkn1+1/k+O(n). We show that γk is at most 80√k·log k, an improvement over the previous bound of k−1. However, the correct order of magnitude for both problems is likely o(n1+1/k) for large k. Appeared in Combin. Probab. Comput., vol. 26(1), pp. 1–15, 2017 (+ erratum on arXiv).
| pdf ps |
| “Longest common subsequences in sets of words” (with Jie Ma) | Among any t binary words of length n over there are two that share a subsequence of length n/2+cn1−1/(t−4) for some c>0. This is sharp, up to value of c. We do not know if c must depend on t. Appeared in SIAM J. Discrete Math., vol. 28(4), pp. 2042–2049, 2014.
| pdf ps talk |
| “Random algebraic construction of extremal graphs” | This article explains why algebraic constructions of Ks,t-free graphs are better than random constructions. In particular, a simple construction of extremal Ks,t-free graphs for t≫s is given. Appeared in Bulletin of the London Math. Soc., vol. 47(6), pp. 939–945, 2015.
| pdf ps |
| “Rational exponents in extremal graph theory” (with David Conlon) | For every rational number r between 1 and 2 there is a graph family whose Turán number is asymptotic to Θ(nr). Appeared in J. of European Math. Society, vol. 20(7), pp. 1747–1757, 2018.
| pdf ps |
| “An improved bound on the fraction of correctable deletions” (with Venkatesan Guruswami and Johan Håstad) | There exist exponentially many binary words of length n such that no two have a common subsequence of length (2−√2+ε)n. Furthermore, there exists an efficient algorithm to recover the word from a subsequence of this length. It is open if 2−√2 can be replaced by 1/2. Appeared in IEEE Trans. Inform. Theory, vol. 63(1), pp. 93–103, 2017.
Preliminary version appeared in SODA'16. | pdf ps |
| “Ranks of matrices with few distinct entries” | Consider the n-by-n matrices whose off-diagonal entries all belong to the set L, and whose diagonal entries are all equal. How small can a rank of such a matrix be? This paper characterizes the sets L for which rank is always linear. As a by-product, it is shown how to construct graphs of size n whose adjacency matrices have eigenvalue √2015 with multiplicity n/2−O(√n). The bound is sharp. Appeared in Israel Journal of Mathematics, vol. 222(1), pp. 165–200, 2017.
| pdf ps code talk video |
| “Bounds on equiangular lines and on related spherical codes” | Every set of lines in Rd whose pairwise angles are all equal to some fixed α has at most cα d lines. Appeared in SIAM J. Discrete Math., vol. 30(1), pp. 549–554, 2016.
| pdf ps |
| “Bipartite algebraic graphs without quadrilaterals” (with Zilin Jiang) | We conjecture that every algebraic hypersurface that gives rise to a Ks,t-free graph is equivalent, in a suitable sense, to a low-degree hypersurface. We establish a version of this conjecture for K2,2-free graphs. Appeared in Discrete Math., vol. 341(6), pp. 1597–1604, 2018.
| pdf ps |
| “One-sided epsilon-approximants” (with Gabriel Nivasch) | Suppose A and P are sets in Rd such that every convex set containing α-fraction of points P contains at least (α−ε)-fraction of points of A, for every α. In such a case, set A is called a one-sided ε-approximant to P. We show that every P admits a one-sided ε-approximant of size depending only on ε and on d. Appeared in A Journey through Discrete Mathematics. A Tribute to Jiří Matoušek., pp. 343–356, 2017.
| pdf ps talk |
| “Classifying unavoidable Tverberg partitions” (with Gabriel Nivasch and Po-Shen Loh) | Every set of (r−1)(d+1)+1 points in Rd admits an r-Tverberg partition, which is a partition into r parts whose convex hulls intersect. In a large set of points, which combinatorial types of r-Tverberg partitions unavoidably occur? We provide partial answers in dimensions up to 4. Appeared in J. Comput. Geom., vol. 8(1), 2017.
| |
| “Shatter functions with polynomial growth rates” (with Xavier Goaoc) | Let f be a shatter function of a set system. Sauer–Shelah lemma says that if f(k+1)<2k+1, then f(n)=O(nk). For integer k, we show that if f(m)≤ (2k+1−k−1)m+Ck, then f(n)=O(nk), and that this is sharp apart from the value of Ck. Appeared in SIAM J. Discrete Math., vol. 33(2), pp. 784–794, 2019.
| |
| “On a topological version of Pach's overlap theorem” (with Alfredo Hubard) | Let φ be a continuous map from an n-vertex simplex to R2. Then there are sets X,Y,Z, of size 10−14(log n) each, and a point p∈R2 such that the φ-image of every triangle of the form xyz contains p. This is false with 50 in place of 10−14. Appeared in Bulletin of the London Math. Soc., vol. 52(2), pp. 275–282, 2019.
| pdf ps |
| “List-decodable zero‑rate codes” (with Noga Alon and Yury Polyanskiy) | Code C⊆{0,1}n is <L-list-decodable with (relative) radius τ if every Hamming ball of radius τn covers fewer than L codewords. We show that the size of the largest <2-list-decodable code with radius ¼+ε is of the order ε−3/2. We also solve the analogous problem with 2 replaced by any odd number, but all the other cases remain a mystery. Appeared in IEEE Trans. Inform. Theory, vol. 65(3), 2019.
| pdf ps code |
| “On a fractional version of Haemers' bound” (with Chris Cox) | It is unknown if there is an algorithm to approximate the Shannon capacity of, say, C7. The obstacle is that only two upper bounds on Shannon capacity are known: Lovász theta function and Haemers' bound. We rediscover a version of Haemers' bound which is originally due to Blasiak. We show that it is strictly stronger than Haemers' bound, and that it is multiplicative, like the Lovász theta function. Appeared in IEEE Trans. Inform. Theory, vol. 65(6), 2019.
| pdf ps |
| “Length of the longest common subsequence between overlapping words” (with Raymond Hogenson) | Suppose U and V are two random words over k-letter alphabet of length n that overlap in a subword of length ℓ. How long is the longest common subsequence between U and V? If ℓ=0, then this is well-studied problem, whose answer is approximately γk⋅n. For general ℓ, we show that the longest common subsequence has length approximately max(γk⋅n,ℓ). Appeared in SIAM J. Discrete Math., vol. 34(1), 2020.
| pdf ps |
| “Nearly orthogonal vectors and small antipodal spherical codes” (with Chris Cox) | How to arrange d+k vectors in Rd so that they are as close to orthogonal as possible? We answer this question when k=1,2,3,7 or 23. This is a consequence of a sharp upper bound on the first moment of isotropic measures, and the existence of large families of equiangular lines in Rk for these values of k. Appeared in Israel Journal of Mathematics, vol. 238(1), pp. 359–388, 2020.
| pdf ps talk |
| “Consistent sets of lines with no colorful incidence” (with Xavier Goaoc, Alfredo Hubard and Matthew Trager) | Call a collection of photographs `consistent' if there is a same scene that these are photographs of (from different points of view). For the case when the `scene' is just a set of points, we construct a collection of 101 photographs such that every 100 of them are consistent, but all of them together are inconsistent. Preliminary version appeared in SoCG'18. | |
| “Turán numbers of theta graphs” (with Michael Tait) | The theta graph consists of two vertices joined by t vertex-disjoint path of same length ℓ. For fixed ℓ and large t a theta-free graph on n vertices has at most cℓ⋅t1−1/ℓn1+1/ℓ edges, and for odd ℓ this is tight apart from the value of cℓ. The case of even ℓ remains open. Appeared in Combin. Probab. Comput., vol. 29(4), pp. 495–507, 2020.
| pdf ps talk |
| “Linear orderings of combinatorial cubes” (with Anish Sevekari) | We show that every linear ordering of [2]n contains a large combinatorial subcube on which the ordering is lexicographic. In the analogous statement for [k]n with k≥3, the lexicographic ordering is not the only possible outcome; asymptotically, there are slightly more than k! many orderings that are stable under passing to a subcube. The main result of the paper appeared in “Canonizing ordering theorems for Hales-Jewett structures” by Nešetřil, Prömel, Rödl, Voigt. | pdf ps |
| “Periodic words, common subsequences and frogs” (with Chris Cox) | How long is the longest common subsequence (LCS) between two random words? We give evidence that it is of length γ⋅n−cn⅓+o(n⅓). We completely solve the analogous problem for the LCS between a random word and a periodic word. Mysteriously, the special case of the word 123…123… leads to a Markov chain on Dyck paths. Appeared in Ann. Appl. Probab., vol. 32(2), pp. 1295–1332, 2022.
| pdf code |
| “Order-isomorphic twins in permutations” (with Oleksandr Rudenko) | Every permutation of 1,…,n contains two disjoint order-isomorphic subsequences of length Ω(n3/5). It likely that this holds with 2/3 in place of 3/5, but we were able to show this only for random permutations. Appeared in SIAM J. Discrete Math., vol. 34(3), 2020.
| pdf ps |
| “On convex holes in d‑dimensional point sets” (with Ting-Wei Chao and Ron Holzman) | There are arbitrarily large sets in Rd that do not contain vertices of an empty convex polyhedron with 4d+o(d) vertices. The lower bound remains linear in d. Appeared in Combin. Probab. Comput., vol. 31(1), 2022.
| pdf ps |
| “Longest common subsequences between words of very unequal length” (with Zichao Dong) | Consider random words over k-symbol alphabet. We show that the expected length of a word of length n and a word of length (1−ε)kn is of the order 1−cε2. For large k, the constant c should tend to 1/4, but we prove only that c≥1/4−o(1). In addition, we present a convenient formalism for constructing couplings of Markov chains. | pdf ps |
| “Empty axis-parallel boxes” (with Ting-Wei Chao) | Given any n points in [0,1]d, there is an empty axis-parallel box of volume Ω(d/n). On the other hand, there exist sets for which the largest such box has volume only O(d2log d/n). Appeared in International Math. Research Notices, pp. 13811–13828, 2022.
| pdf ps |
| “Digital almost nets” (with Ting-Wei Chao) | An almost net is a set of 2nm points in [0,1]d intersecting every dyadic box of volume 2−n in approximately m points. There exist almost nets with m=O(d log d), improving the exponential bound from the usual nets. The lower bound on m is logarithmic. Appeared in Electronic J. of Combinatorics, vol. 29, R4.27, 2022.
| pdf ps |
| “Extremal graphs without exponentially-small bicliques” | There are extremal Ks,t-free graphs with t≈9s. This improves on the factorial-type bounds on t. A curious ingredient of the construction is a bound on the number of non-trivial representations of zero as a power sum of linear forms. Appeared in Duke Math. Journal, vol. 173(11), pp. 2039–2062, 2024.
| pdf talk survey |
| “Sharp density bounds on the finite field Kakeya problem” (with Ting-Wei Chao) | Every Kakeya set in Fqn has at least 2−n+1qn elements. This is sharp up to O(qn−1) terms. Appeared in Discrete Anal., 2021:26.
| pdf ps talk |
| “Applications of random algebraic constructions to hardness of approximation” (with Bhargav Narayanan and Karthik C.S.) | Given disjoint sets A1,...,Ak and B of equal size, one can make a bipartite graph with parts A=∪Ai and B such that the common neighborhood of a k-set in A is large only if the k vertices belong to the distinct sets among A1,...,Ak. This is used to show computational hardness results for several problems. Accepted to Israel Journal of Mathematics
Preliminary version appeared in FOCS'21. | |
| “Enumeration of interval graphs and d‑representable complexes” (with Amzi Jeffs) | We show that there are exp(cd⋅nd log n) ways to arrange n convex sets in Rd, and that this is sharp up to the value of the constant cd. Accepted to Israel Journal of Mathematics
| pdf ps |
| “Convex polytopes in restricted point sets in Rd” (with Zichao Dong) | There are non-elongated n-element sets in Rd that contain no subset of size O(n1−2/(d+1)) in convex position, and this is sharp. Here, ‘non-elongated’ means that the largest distance between the points is at most O(n1/d) times larger than the smallest. | pdf ps |
| “Planar convex codes are decidable” (with Amzi Jeffs) | Given an abstract Venn diagram, can it be realized by convex sets in Rd? We show that this problem is decidable for d=2, and explain why it is likely harder in higher dimensions. Appeared in SIAM J. Discrete Math., vol. 37(2), 2023.
| pdf ps |
| “Distances between realizations of order types” (with Amzi Jeffs) | One can move any n-tuple of points in R2 such any triple changes orientation at most once, on average. This is twice better than the obvious linear motion. On the other hand, there are n-tuples requiring cubically many intermediate changes. | pdf ps |
| “New bounds for the same-type lemma” (with Alexey Vasileuski) | Any m sets in the plane contain constant-fraction-sized subsets Y1,...,Ym such that the orientations of a triangle spanned by points from sets Yi, Yj and Yk depends only on the indices i, j, k, but not on the actual choice of the points. We show that the best constant fraction is between Ω(m−4) and O(m−2). | pdf ps |
| “Colouring random subgraphs” (with Bhargav Narayanan and Michael Krivelevich) | For a graph G, and let G1/2 be its random subgraph. If G is hard to color, must G1/2 be hard to color too? In the context of greedy colorings, we give an example of a graph whose coloring number (=degeneracy) is k, but whose random subgraph is almost surely has coloring number ≈k/3. | pdf ps |
| “Additive bases: change of domain” (with Peter van Hintum and Peter Keevash) | Given a set of numbers A, what is the smallest set B satisfying A⊆B+B? For the same set A, the answer might depend on what one means by `numbers'. For example, we show that changing `rationals' by `natural numbers' can require almost doubling the size of B, which is as bad as it can get. | pdf ps |
If you find any paper above hard to read, write to me, as that means the paper is poorly written, not that the result is hard.
