7th Combinatorial Algorithms Day

Session 1 (CAB G51)

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.

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.

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|²|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.

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 R^d, then there is a partition of S into r parts A₁,...,A_r 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 R^d 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 R^d 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 R^d without r-fold Tverberg point, where k=(r-1)m, d=rm, m>=3.
Joint work with Isaac Mabillard.

Session 2 (CAB G51)

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.

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(m^2/3n^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 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.

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 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.

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.

Session 3 (Val Sinestra, Wintergarten)

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.

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.

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.