Session 1 (CAB G51) 
08:5509:00 
Opening:
Emo Welzl 
09:0009:20 
Saturation Games on Graphs
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002  Sept 30, 2005)
Abstract:
Let P be a graph property. The game is played by two players, Max
and Mini. They start with an empty graph on n vertices and
alternately add missing edges, with the following restriction: the
graph should not possess property P at any point of the game. The
game ends when no missing edge can be added. Max wants the game to
last for as long as possible, while Mini's goal is to end the game
as soon as possible. When both players play optimally, the total
number of edges played to the end of the game is denoted by
s(P,n).
We want to estimate s(P,n) for some standard graph properties
$P$, like "being kconnected", "not being kcolorable",
"containing a kmatching". In doing so we demonstrate that
s(P,n) can be as large as the Turan number or as low as the
saturation number, and also that it might strongly depend on the
identity of the first player.
Joint work with Dan Hefetz, Michael Krivelevich and Alon
Naor.

09:2009:40 
Generalizing Bipartiteness to Higher Dimensions
Anna Gundert, Universität zu Köln
(Gremo Jan 4, 2010  Dec 31, 2013)
Abstract:
Bipartiteness for graphs can be characterized using several
different properties, e.g., spectral properties, the existence of
certain edge orientations and of course the usual combinatorial
definition. We will consider generalizations of these properties to
higherdimensional simplicial complexes. Even though the
equivalences of the graph case no longer hold, we can still observe
connections. We describe a higherdimensional analogue of a result
by Trevisan which establishes an inequality very much like the
discrete Cheeger inequality. His result connects the largest
Laplacian eigenvalue and the socalled bipartiteness ratio,
measuring how close a graph is to being bipartite. We show that one
part of this inequality also holds in higher
dimensions.

09:4010:00 
Extended Formulations for Sparsity Matroids
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002  Mar 31, 2005)
Abstract:
We show the existence of a polynomialsize extended formulation
for the base polytope of a (k,l)sparsity matroid. For an
undirected graph G=(V,E), the size of the formulation is
O(VE) when k >= l and O(V^{2}E) when k <= l.
To this end, we employ the technique developed by Faenza et
al. recently that uses a randomized communication protocol.
Joint work with Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, and
Shuji Kijima.

10:0010:20 
Eliminating Tverberg Points
Uli Wagner, IST Austria
(Gremo Apr 1, 2000  Jul 31, 2003 and Apr 1, 2006  Jun 31, 2012)
Abstract:
Tverberg's theorem, a generalization of Radon's Lemma and a
cornerstone of convex geometry, states that if N=(d+1)(r1) and
if S is any set of N+1 points in R^{d}, then there is a
partition of S into r parts A_{1},...,A_{r} whose convex hulls
have a point in common.
This can be restated as saying that for any affine map from the
Nsimplex Δ^{N} to R^{d} has an rfold Tverberg point,
i.e., there are r pairwise disjoint faces whose images have a
point in common.
The topological Tverberg problem asks if this conclusion remains
true if we allow arbitrary continuous maps; this is known to be
true if r is a prime or a prime power, but in general remains an
important open problem in topological combinatorics.
One can also consider more general Tverbergtype questions and
replace the simplex Δ^{N} by some other simplicial complex
K and ask whether K admits a Tverbergtype theorem, i.e., if
any map f from K to R^{d} has an rfold Tverberg point,
i.e., if there are r disjoint faces of K whose images
intersect. In particular, we can ask: is there an algorithm to
decide this, for a given input K, r, and d?
Here, we propose to generalize classical results concerning
embeddings (the case r=2) to Tverbergtype selfintersection
points of maps; in particular, we present an rfold
generalization of the classical Whitney trick. As a corollary,
this yields an algorithm for deciding whether a kdimensional
complex admits a map into R^{d} without rfold Tverberg point,
where k=(r1)m, d=rm, m>=3.
Joint work with Isaac Mabillard.

10:2010:50 
Coffee Break 
Session 2 (CAB G51) 
10:5011:10 
Towards the HananiTutte Theorem for Clustered Graphs
Radoslav Fulek, Columbia University
Abstract:
The weak variant of HananiTutte theorem says that a graph is
planar, if it can be drawn in the plane so that every pair of edges
cross an even number of times. Moreover, we can turn such a
drawing into an embedding without changing the order in which edges
leave the vertices. We prove a generalization of the weak
HananiTutte theorem that also easily implies the monotone variant
of the weak HananiTutte theorem by Pach and Tóth. Thus, our
result can be thought of as a common generalization of these two
results. In other words, we prove the weak HananiTutte theorem
for clustered graphs, whose clusters are linearly ordered and edges
join only vertices in the same cluster or in neighboring clusters
with respect to this order. Besides usual tools for proving
HananiTutte type results our proof combines Hall's marriage
theorem, and a characterization of embedded upward planar digraphs
due to Bertolazzi et al.

11:1011:30 
On Distinct Distances Between Points and Lines
Shakhar Smorodinsky, Ben Gurion University
(Gremo Feb 15, 2004  Oct 31, 2004)
Abstract:
The SzemerediTrotter bound on pointline incidences is equivalent
to the following fact: Given m points and n lines, the number
of pointline pairs (p,l) such that the Euclidean distance
from p to l is 1 is O(m^{2/3}n^{2/3}+m+n). It is natural
to ask the following analog of the Erdős' distinct distances
problem: What is the minimum number of distinct pointline
distances that is always determined by m points
and n lines? We make the first attempt to tackle this problem.
Joint work with Micha Sharir.

11:3011:50 
Disjoint Edges in Topological Graphs and the TangledThrackle Conjecture
Andres RuizVargas, EPF Lausanne
Abstract:
It is shown that for any positive integer t, every simple
topological graph on n vertices has O(n) edges if it has no two
sets of t edges such that every edge in one set is disjoint from
all edges of the other set (i.e., the complement of the
intersection graph of the edges is K_{t,t}free). As an
application, we settle the tangledthrackle conjecture formulated
by Pach, Radoičić, and Tóth: Every nvertex graph drawn
in the plane such that every pair of edges have precisely one point
in common, where this point is either a common endpoint, a
crossing, or a point of tangency, has at most O(n)
edges.

11:5012:10 
Approximate Interior Barriers
Csaba Dávid Tóth, CSU Northridge
(Gremo Mar 1, 2000  Aug 31, 2002)
Abstract:
The problem of finding a collection of curves of minimum total
length that meet all the lines intersecting a given polygon was
initiated by Mazurkiewicz in 1916. Such a collection forms an
opaque barrier for the polygon. In 1991 Shermer proposed an
exponentialtime algorithm that computes an interiorrestricted
barrier made of segments for a given convex ngon. He
conjectured that the barrier found by his algorithm is optimal,
however this was refuted recently by Provan et al. We give a
Shermerlike algorithm that computes an interior polygonal barrier
whose length is at most 1.7168 times the optimal and that runs
in O(n) time.
Joint work with A. Dumitrescu and M. Jiang.

12:1012:15 
Organizational Remarks:
Michael Hoffmann 
Session 3 (Val Sinestra, Wintergarten) 
17:3017:50 
On extensions of the ElekesSzabó Theorem
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000  Mar 31, 2001)
Abstract:
The ElekesSzabó Theorem states that an algebraic variety in the
3space might have large intersection with a large Cartesian
product only if it has a special form. I will review some recent
developments about extensions and applications of this result.

17:5018:10 
Clustering by Iterative Graph Modification
Takeaki Uno, NII Tokyo
(Gremo May 9, 2005  Aug 3, 2006)
Abstract:
Dense subgraphs in a graph are regarded as important in data
mining, such as they should be clusters, thus there are many
approaches for extracting/enumerating them. However, simple models
usually encounter some difficulties such as the explosion of the
number of solutions, heavy computational cost, and skewed sizes of
obtained structures. Currently there is no standard efficient
method for solving this problem. In this talk, we propose a new
approach to "clarify" the dense structures as they should be. The
approach is named graph polishing, that is, to fill missing
edges in a dense subgraph and delete edges included in no dense
subgraph. The algorithm is a simple combinatorial algorithm but
efficient on realworld data, so that it can solve the above
difficulties. The experimental results show the efficiency of the
proposed algorithm.

18:1018:30 
On the Cycles of Degree3 Critical Graphs
Tibor Szabó, FU Berlin
(Gremo Sep 1, 2000  Aug 31, 2008)
Abstract:
We study graphs on n vertices having 2n2 edges and no proper
induced subgraphs of minimum degree 3. Erdős, Faudree,
Gyárfás, and Schelp conjectured that such graphs always have
cycles of lengths 3,4,5,...,C(n) for some increasing function
C(n). We disprove this conjecture, resolve a related problem
about leaftoleaf path lengths in trees, and characterize graphs
with $n$ vertices and 2n2 edges, containing no proper
subgraph of minimum degree 3.
Joint work with Lothar Narins and Alexey Pokrovskiy.
