Session 1 (CAB G51) |
08:55-09:00 |
Opening:
Emo Welzl |
09:00-09: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 k-connected", "not being k-colorable",
"containing a k-matching". 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:20-09: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
higher-dimensional simplicial complexes. Even though the
equivalences of the graph case no longer hold, we can still observe
connections. We describe a higher-dimensional 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 so-called 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:40-10:00 |
Extended Formulations for Sparsity Matroids
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002 - Mar 31, 2005)
Abstract:
We show the existence of a polynomial-size 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(|V||E|) 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:00-10: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)(r-1) and
if S is any set of N+1 points in Rd, then there is a
partition of S into r parts A1,...,Ar whose convex hulls
have a point in common.
This can be restated as saying that for any affine map from the
N-simplex ΔN to Rd has an r-fold 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 Tverberg-type questions and
replace the simplex ΔN by some other simplicial complex
K and ask whether K admits a Tverberg-type theorem, i.e., if
any map f from K to Rd has an r-fold 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 Tverberg-type self-intersection
points of maps; in particular, we present an r-fold
generalization of the classical Whitney trick. As a corollary,
this yields an algorithm for deciding whether a k-dimensional
complex admits a map into Rd without r-fold Tverberg point,
where k=(r-1)m, d=rm, m>=3.
Joint work with Isaac Mabillard.
|
10:20-10:50 |
Coffee Break |
Session 2 (CAB G51) |
10:50-11:10 |
Towards the Hanani-Tutte Theorem for Clustered Graphs
Radoslav Fulek, Columbia University
Abstract:
The weak variant of Hanani-Tutte 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
Hanani-Tutte theorem that also easily implies the monotone variant
of the weak Hanani-Tutte 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 Hanani-Tutte 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
Hanani-Tutte type results our proof combines Hall's marriage
theorem, and a characterization of embedded upward planar digraphs
due to Bertolazzi et al.
|
11:10-11:30 |
On Distinct Distances Between Points and Lines
Shakhar Smorodinsky, Ben Gurion University
(Gremo Feb 15, 2004 - Oct 31, 2004)
Abstract:
The Szemeredi-Trotter bound on point-line incidences is equivalent
to the following fact: Given m points and n lines, the number
of point-line pairs (p,l) such that the Euclidean distance
from p to l is 1 is O(m2/3n2/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 point-line
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:30-11:50 |
Disjoint Edges in Topological Graphs and the Tangled-Thrackle Conjecture
Andres Ruiz-Vargas, 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 Kt,t-free). As an
application, we settle the tangled-thrackle conjecture formulated
by Pach, Radoičić, and Tóth: Every n-vertex 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:50-12: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
exponential-time algorithm that computes an interior-restricted
barrier made of segments for a given convex n-gon. He
conjectured that the barrier found by his algorithm is optimal,
however this was refuted recently by Provan et al. We give a
Shermer-like 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:10-12:15 |
Organizational Remarks:
Michael Hoffmann |
Session 3 (Val Sinestra, Wintergarten) |
17:30-17:50 |
On extensions of the Elekes-Szabó Theorem
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000 - Mar 31, 2001)
Abstract:
The Elekes-Szabó Theorem states that an algebraic variety in the
3-space 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:50-18: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 real-world data, so that it can solve the above
difficulties. The experimental results show the efficiency of the
proposed algorithm.
|
18:10-18:30 |
On the Cycles of Degree-3 Critical Graphs
Tibor Szabó, FU Berlin
(Gremo Sep 1, 2000 -- Aug 31, 2008)
Abstract:
We study graphs on n vertices having 2n-2 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 leaf-to-leaf path lengths in trees, and characterize graphs
with $n$ vertices and 2n-2 edges, containing no proper
subgraph of minimum degree 3.
Joint work with Lothar Narins and Alexey Pokrovskiy.
|