14 of May, 2013.
14:15 MA B1 524
Pham Thang (Ha Noi, Vietnam)
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.
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.
The union of any $n$ arithmetic progressions, each of length $n$, with
pairwise distinct differences must consist of at least
$c(ε)n2-ε elements.
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
This is a joint work with Shoni Gilboa.
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.
