| 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. Accepted to Israel Journal of Mathematics. | 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 |
| “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|. Accepted to Israel Journal of Mathematics. | 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. | pdf ps extra talk |
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.
E-mail:
