If you find any paper below hard to read, write to me, as that means the paper is poorly written, not that the result is hard.
TitleSummaryDownload
“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 k3 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+100A has at least 101|A|−o(|A|) elements, where 100A={100 a : aA} is the 100-dilate of A. The bound is sharp. If |A+A|≤K|A|, then |A+100A|≤K22|A|. Plünnecke's inequality yields only |A+100A|≤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
“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 logd1r, where a set N is a weak ε-net for S if N meets every convex set C with |CS|≥ε|S|.
Appeared in Israel Journal of Mathematics, vol. 182, pp. 199–228, 2011.
pdf talk
“Sum-product estimates for rational functions”
(with Jacob Tsimerman)
For a set AFp 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 obtains 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 (k1)(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
“Space crossing numbers”
(with Alfredo Hubard)
The crossing lemma says that in every drawing of a graph with n vertices and m4n 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.
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.
pdf
“Turán numbers for Ks,t-free graphs: topological obstructions and algebraic constructions”
(with Pavle Blagojević and Roman Karasev)
For no s4 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 ts4s.
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 Ω(k2/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 80k·log k, an improvement over the previous bound of k1. 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+cn11/(t4) 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 ts 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). 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. pdf ps code talk
“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.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.
Accepted to A Journey through Discrete Mathematics. A Tribute to Jiří Matoušek.
pdf ps talk
“Classifying unavoidable Tverberg partitions”
(with Gabriel Nivasch and Po-Shen Loh)
Every set of (r1)(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.
pdf
“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+1k1)m+Ck, then f(n)=O(nk), and that this is sharp apart from the value of Ck.pdf
“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 1014(log n) each, and a point pR2 such that the φ-image of every triangle of the form xyz contains p. This is false with 50 in place of 1014.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.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.

Back to the homepage

E-mail: