Seminars in 2013

   14 of May, 2013.

14:15 MA B1 524

Sum-Product Estimates over Finite Rings

Pham Thang (Ha Noi, Vietnam)

The purpose of this talk is to present some new Szemerédi-Trotter type theorems
and Sum – Product estimates over finite rings Zm, where m is positive integer.

16 of July, 2013.

14:15 MA B1 524

Michael Hoffman (ETH Zurich)

Planar Packing of Binary Trees

 In the graph packing problem we are given several graphs and have to map them
 into a single host graph G such that each edge of G is used at most
 once. Much research has been devoted to the packing of trees, especially to
 the case where the host graph must be planar. More formally, the problem is:
 Given any two trees T1 and T2 on n vertices, we want a simple planar
 graph G on n vertices such that the edges of G can be colored with two
 colors and the subgraph induced by the edges colored i is isomorphic to
 Ti, for i in {1,2}.

 A clear exception that must be made is the star tree which cannot be packed
 together with any other tree. But a popular hypothesis states that this is the
 only exception, and all other pairs of trees admit a planar packing.

 I will present/sketch a proof of this conjecture for binary trees (maximum degree three), which
 is joint work with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba Toth.


17 of July, 2013.

14:15 MA B1 524 

Andrzej Grzesik (Jagiellonian University, Krakow)

Flag algebras in extremal graph problems

Flag algebras is a concept developed by Aleksander Razborov to formalize and unify several standard techniques of extremal combinatorics. They allow us to approximate densities of combinatorial structures in huge graphs by counting specific small substructures, so-called flags. In a typical application, a density problem is reduced to minimizing an appropriate linear operator. The latter can be highly computerized with the use of linear or semidefinite programming. The method turned out to be extremely powerful and led to solutions of quite a few long-standing problems. In this talk, I will present basic ideas and intuitions behind flag algebras, and show how to apply them to prove some old and new extremal graph-theoretic results.

24 of September, 2013.
17:00 MA B1 524

Andrey Kupavskii (DCG)

Unit distance graphs 

A complete (unit) distance graph in Rd is a graph whose set of vertices is a finite subset of the d-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph in Rd is any subgraph of such a graph. We show that for any fixed d the number of complete distance graphs in Rd on n labelled vertices is $2(1+o(1)) d n \log_2 n, and give a short proof of the known fact that the number of distance graphs in Rd on n labelled vertices is 2(1-1/\lfloor d/2\rfloor +o(1))n^2/2. We will also study several other extremal problems involving distance graphs. (Joint work with Noga Alon)


8 of October, 2013.  

17:00 MA B1 524
Rom Pinchasi (Technion, Haifa) 
 We show that for every $ε>0$ there is an absolute constant
 $c(ε)>0$ such that the following is true:
 The union of any $n$ arithmetic progressions, each of length $n$, with
 pairwise distinct differences must consist of at least
 $c(ε)n2-ε elements.
 We show also that this type of bound is essentially best possible, as we
 can observe n arithmetic progressions, each of length n, with pairwise
 distinct differences such that the cardinality of their union is o(n2).

 We develop some number theoretical tools that are of independent interest.
 In particular we give almost tight bounds on the following question: Given
 n distinct integers a1,…,an at most how many pairs satisfy
 aj/ai in [n]$? More tight bounds on natural related problems
 will be presented.

This is a joint work with Shoni Gilboa.



20 of November 2013.
11:00 MA B1 524 



Kolja Knauer (University of Montpellier)
Making Octants Colorful

 We prove that for any positive integer k, every finite set of points
in R^3 can be colored with k colors so that every
translate of the negative octant containing at least k^6 points
contains at least one point of each color. The best previously known
bound was doubly exponential in k. This yields, among other
corollaries, the first polynomial bound for the decomposability of
multiple covers by homothetic triangles. We also investigate related
decomposition problems involving intervals appearing on a line.
        This is joint work with Jean Cardinal, Piotr Micek, and
Torsten Ueckerdt.

 11:15 on the 4th of December 2013 in MA B1 524

Distinct values on algebraic curves
Claudiu Valculescu (DCG) (joint work with Frank de Zeeuw)
Given an algebraic curve with n points on it, we prove that the number of distinct areas of triangles determined by the origin and two of the points is at least cn^{4/3}, unless the curve has a special form, thus improving a bound given by Charalambides (c n^{5/4}). Moreover, we prove the same statement for more general functions of pairs of points on algebraic curves, for example bilinear functions, and discuss other possible extensions of our result, including to quadratic functions and in higher dimensions. Our proofs generalize the method that Pach and De Zeeuw recently applied to the distinct distance problem on algebraic curves


 11 December 2013
11:15 MA B1 524
A geometric proof for linear programming duality.

Gergely Ambrus (DCG)


One of the fundamental results in the theory of linear programming is the duality theorem from the beginning of the 1950’s. There are several proofs available, however, neither of them provides a transparent understanding of the connection between the primal and the dual problems. In this short talk, we will see an intuitive, geometric argument that shows that LP duality can be derived from the classical geometric duality (polarity) in a simple way.