December 10, 2014
”Solving the stable set problem in terms of the odd cycle packing number.”
Andres J. Ruiz-Vargas (EPFL)
Abstract: The stable set problem is as follows: given an undirected graph G find a maximum cardinality set of pairwise non-adjacent vertices. The problem is NP-hard to approximate with factor n1−ε for any ε > 0 [10, 22], where n is the number of vertices, and therefore there is no hope for good approximations in the general case. We study the stable set problem when restricted to graphs with bounded odd cycle packingnumber ocp(G), possibly by a function of n. This is the largest number of vertex-disjoint odd cycles in G. Equivalently, it is equal to the logarithm of the largest absolute value of a sub-determinant of the edge-node incidence matrix AG of G. Hence, if AG is totally unimodular ocp(G) = 0. Therefore, ocp(G) is a natural distance measure of AG to the set of totally unimodular matrices on a scale from 1 to n/3.
When ocp(G) = 0, the graph is bipartite and it is well known that stable set can be solved in polynomial time. Our results imply that the odd cycle packing number indeed strongly influences the approximability of stable set. More precisely, we obtain (i) a polynomial-time approximation scheme for graphs with ocp(G) = o(n/logn). And (ii) an α-approximation algorithm for any graph where α smoothly increases from a constant to n as ocp(G) grows from O(n/ log n) to n/3. On the hardness side, we show that (iii) assuming the exponential-time hypothesis, stable set cannot be solved in polynomial time if ocp(G) = Ω(log1+ε n) for some ε > 0. Finally, we (iv) generalize a theorem by Györi et al. [8] and show that graphs without odd cycles of small weight can be made bipartite by removing a small number of vertices. This allows us to extend some of our above results to the weighted stable set problem.
This is joint work with Adrian Bock, Yuri Faenza, Carsten Moldenhauer.
December 3
”The Erdos-Szekeres Theorem, and a generalization for lines.”
Géza Tóth (Rényi Institute, Budapest)
Abstract: According to the Erdos-Szekeres Theorem (1935),for every n there is a (smallest) f(n) such that any set of f(n) points in the plane (in general position) contains $n$ in convex position. Erdos and Szekeres proved that
2^{n-2}+1\le f(n)\le {2n-4\choose n-2}+1 \approx 4^n/\sqrt{n}.
(Then Szekeres married Esther Klein, who posed the problem.)
The lower bound has not been improved and it is conjectured to be the truth.
Recently the upper has been improved a little bit, to
{2n-5\choose n-2}+1
in several steps. We review these improvements, some related problems, and then
we investigate the “dual” version of the problem.
We say that n lines are in convex position if they bound a convex n-gon.
Let f_l(n) be the smallest number with the property that this many lines
in general position always contain n in convex position.
We show a lower and upper bound for f_l(n)
of roughly 4^n/n and 4^n/\sqrt{n}, respectively.
So we have a much better lower bound for lines then the one for points.
We also try to ”dualize” some of the generalizations, different versions of the original Erdos-Szekeres Theorem.
Joint work with Imre Barany and Edgardo Roldan-Pensado.
November 26
Nabil Mustafa (ESIEE, Paris)
The problem is that given a set system, one would like to color each vertex with a color red or blue such that the colors are roughly balanced in each set of the system. This gives a constructive algorithm for the 1980s result of Beck which used purely combinatorial arguments to prove the existence of balanced colorings, but without an efficient algorithm.
“The Multiplicative Weights Technique in Discrete and Computational Geometry”
Nabil Mustafa (ESIEE, Paris)
Abstract: I will explain a simple broad technique for converting claims of one type to a different dual-like set of claims. While this technique has had several applications in various areas in Computer Science, I will only focus on some applications in discrete and computational geometry. In particular, I will describe three results: a classical result of Haussler-Welzl on spanning trees (1987), the Alon-Kleitman proof of Hadwiger-Debrunner conjecture (1992), and a result on extending some classical theorems (e.g.,Radon’s theorem, Caratheodory’s theorem) in discrete geometry (joint work with Saurabh Ray).
November 19
“Conflict Free Coloring”
Shakhar Smorodinsky
Abstract: There are few generalizations of the classical graph coloring notion to arbitrary hypergraphs. One such generalization is the conflict-free coloring notion. This notion originated recently in the context of frequency assignment in cellular networks. It attracted a lot of attention both from mathematicians and computer scientists. In this talk I will introduce this notion and if time permits, I will also introduce the list-coloring version of this notion. No prior knowledge is needed. In fact, prior knowledge is bad for you.
November 12
“How many ways can one simply draw a graph?”
Jan Kynčl
November 5
“The parametrized complexity of k-biclique”
Alfonso Cevallos
Abstract: Given a graph G and a parameter k, the k-biclique problem asks whether G contains a subgraph isomorphic to the complete bipartite subgraph K_{k,k}. We present a lower bound on its parametrized complexity, based on an fpt-reduction from k-clique to k-biclique: Assuming the Exponential Time Hypothesis, there is no f(k) * n^(o(k))-time algorithm to solve the (k!)-biclique problem, for any computable function f.
The result is by Bingkai Lin, and won the best paper award in SODA ’15.
October 29
“Number of double-normals in a set of n points in space”
Andrey Kupavskii
Abstract: Two points p,q in a subset S of R^d form a double-normal, if S lies between two parallel hyperplanes passing through p and q and that are orthogonal to pq. We refine the results on the number of double-normals in an n-point set in R^d that are due to J. Pach and K. Swanepoel. The problem appears to be closely connected with the P. Erdos’ problem on the number of points in R^d that form only non-obtuse angles.
October 16
“Discrete geometry on 3 colored point sets in the plane”
Mikio Kano (Ibaraki university, Japan)
We will present three different theorems, one of which follows. For any three sets of points in the plane, each of n ≥ 2 points such that any three points (from the union of three sets) are not collinear and the convex hull of 3n points is monochromatic, there exists an integer k ∈ {1, 2, . . . , n − 1} and an open half-plane containing exactly k points from each set.
We call a coloring of edges of a given graph proper, whenever parts colored by each of the colors contain no cycles. Inspired by on-line graph vertex coloring games we consider several two player games, in which Presenter disclose some information about the graph (for example: which edge belongs to the graph, lists of colors available at an edge, a set of edges that may be colored with a given color, etc.) and Algorithm’s goal is to properly color all edges of the graph. We will relate the number of colors that assures the existence of a winning strategy for Algorithm with the minimum number of colors needed to properly color the graph off-line.
Claudiu Valculescu (EPFL)
Based on the definition of non-degenerate hyperplanes introduced by Elekes and Toth, Agarwal et al introduced the notion of non-degenerate spheres. In this talk, I am going to briefly present those notions, together with a new type of degeneracy, recently introduced by Basit and Sheffer. I will also state and sketch the proof of some results of the latter about incidences in three dimensions between non-degenerate spheres and points, respectively non-degenerate planes and points, in the case of this new type of degeneracy, using polynomial partitioning.”
