Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Program — Combinatorial Algorithms Day 2014

7th Combinatorial Algorithms Day

Monday, June 30th 2014

The first two sessions are in CAB G51 (the usual Mittagsseminar room). The last session is in Val Sinestra.
Here is a PDF-map of ETH Zentrum.

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)

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)

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)

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)

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

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)

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

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)

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)

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)

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)

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.

Valid HTML 4.01!