In Prague
The people coming.
In October, from 27th to 28th.
Informal atmosphere with free time to work & cooperate. See the programme and the poster.
bla
bla
9h30 | Jiri Sgall |
---|---|
10h15 | Nicolas Trotignon |
11h | Cofee Break |
11h15 | Pierre Aboulker |
12h | Martin Loebl |
12h45 | Lunch |
14h | Open Problem Session + Discussions |
15h | Visit of Strahov Library |
19h | dinner |
9h | Patrice Ossona de Mendez |
---|---|
9h45 | Jaroslav Nešetřil |
10h30 | Cofee Break |
10h45 | Lluis Vena |
11h30 | Reza Naserasr |
12h15 | Zdeněk Dvořák |
13h | Lunch |
14h30 | Michael Pinsker |
15h15 | Discussions |
A balanced separation in a graph $G$ is a pair $(A,B)$, where $A\cup B=V(G)$, no edge of $G$ has one end in $A\setminus B$ and the other end in $B\setminus A$, and $\max(|A\setminus B|, |B\setminus A|)\le 2|V(G)|/3$. The order of the separation is $|A\cap B|$. Graphs in many interesting graph families (graphs embeddable in any fixed surface, \ldots) are known to have small balaced separations.
We give two results relating balanced separations to other graph parameters:
In the bin packing problem we are given an instance consisting of a sequence of items with sizes between $0$ and $1$. The objective is to pack these items into the smallest possible number of bins of unit size. {\sc FirstFit} and {\sc BestFit} algorithms are simple online algorithms introduced in early seventies, when it was also shown that their asymptotic approximation ratio is equal to 1.7. We present a simple proof of this bound and survey recent developments that lead to the proof that also the absolute approximation ratio of these algorithms is exactly 1.7. More precisely, if the optimum needs OPT bins, the algorithms use at most $\lfloor1.7\cdot\mbox{\sc OPT}\rfloor$ bins and for each value of OPT, there are instances that actually need so many bins.
We express weight enumerator of each binary linear code as infinite product. A special case of cycle space of planar graphs was done in the beginning of 60's by R. Feynman.
A celebrated Theorem of de Bruijn and Erdos states that every noncollinear set of n points in the plane determines at least n distinct lines.
Line uv in the plane consists of all points p such that
With this definition of line uv in an arbitrary metric space (V, dist), Chen and Chvatal conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points.
We will discuss the Chen-Chvatal conjecture, its various special cases, the efforts and results in trying to generalize the classical De Bruijn-Erdos theorem, and many recent variations on the topic.
We prove that any graph G with minimum degree greater than 2k^2-1 has a (k+1)-connected induced subgraph H such that the number of vertices of H that have neighbors outside of H is at most 2k^2 − 1. This generalizes a classical result of Mader stating that a high minimum degree implies a highly connected subgraph. We give several variants of our result, and for each of them, we give asymptotics for the bounds.
It was proven by Alon, Kleitman, Saks, Seymour and Thomassen that in a graph of high chromatic number, there exists an induced subgraph with high connectivity and high chromatic number. Our results give a new proof of this theorem with a better bound.
(joint work with Irena Penev and Stéphan Thomassé)It is known that a countable $\omega$-categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.