| 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 |
| “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. | 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. Accepted to Proceedings of the London Math. Soc.. | 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. Accepted to SIAM J. Discrete Math | pdf ps |
| “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 |
| “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. Accepted to Combin. Probab. Comput. | 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. | |
| “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. | 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.
E-mail:
