# Seminars of 2014

December 12

”Cross-intersecting families of vectors.”

Gábor Tardos (Rènyi Institute of Mathematics, Budapest)

Abstract: We consider families vectors (x_1,…,x_n) with x_i from [p_i]={1,2,…,p_i} and say that the families A and B of such vectors are r-cross-intersecting if for any vector x from A and y from B the number of common coordinates of x and y is at least r.

We are interested in the maximum of |A||B| for r-cross-intersecting families and in the structure of the extremal families. This (as most problems in extremal set theory) can be considered as a variant of the the problem considered in the famous Erdos-Ko-Rado theorem.

A simple construction of cross-intersecting families is taking balls B(x,T,l) consisting of all vectors y such that y_i=x_i for all indices i in T except for at most l of them. Clearly, B(x,T,l) and B(x,T,l’) are |T|-l-l’ -cross-intersecting. A natural conjecture is that the maximum |A||B| is achieved with well chosen balls and perhaps it is only achieved with balls. While the stronger statement is false if r=1 and there are more than one coordinates with p_i=2, we believe that it is true otherwise (and the first statement is true always). We prove this conjecture in several special cases but the general conjecture remains open.

These are joint results with Janos Pach.

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

”Discrepancy by random walks.”

Nabil Mustafa (ESIEE, Paris)

Abstract: In this talk I will explain the paper:
Constructive Discrepancy Minimization by Walking on The Edges, by Lovett and Meka.

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.

June 25
The application of hypergraph and the combination of Graph-theoretic method and Fourier method

Thắng Phạm (DCG, EPFL)

We will show some applications of hypergraph to recent problems and the connection between Graph-theoretic method and Fourier method for the problems over finite fields and related results. We also talk about a beautiful conjecture about Mengerian Hypergraph.

May 27

“On the Richter-Thomassen conjecture about pairwise intersecting closed curves”

Gabor Tardos (Alfred Renyi Institute of mathematics)

A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed (i.e., Jordan) curves in the plane which are in general position and any pair of them intersect, is at least (2 − o(1))n. We confirm the above conjecture in several important cases including x-monotone curves, curves that are boundaries of convex sets, and, more generally, curves which can be decomposed into constantly many x-monotone pieces. In each of these cases, we show that the overall number of proper intersection points must exceed, in asymptotic terms, the number of the touching pairs of curves.

This is joint work with Janos Pach and Natan Rubin

May 15

Indecomposable coverings using unit discs

Domotor Palvolgyi (Eotvos University, Budapest)

Let C=Ci be a collection of sets in R2. We say that C is an m-fold covering if every point of R2 is contained in at least m members of C. A 1-fold covering is simply called a covering.

A planar set C is said to be cover-decomposable if there exists a (minimal) constant m=m(C) such that every m-fold covering of the plane with translates of C can be decomposed into two coverings.

The problem of characterizing all cover-decomposable sets in the plane was proposed by Pach in 1980. He conjectured that every planar convex set C is cover-decomposable. We disprove this conjecture by showing it holds for no convex set with a smooth boundary, so for example the unit disc.

April 16

“On-line graph arboricity”

Wojciech Lubawski (Jagiellonian University)

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.

March 20

Optimal specturm for simplicial complexes.

Uriya First

Expanding graphs can be described via spectral properties of their adjacency matrix. Ramanujan graphs are graphs with “optimal” spectrum and are, in this sense, optimal expanders. The optimal spectrum is derived from the Alon-Boppana Theorem.
When attempting to generalize the theory for simplicial complexes, one has to choose which linear operators associated with the complex would take the place of the graph adjacency matrix. So far, different authors have used different operators, in turn leading to different notions of spectrum and (sometimes) optimal spectrum.
I will survey some of these works, focusing especially on the Ramanujan complexes of Lubotzky-Samuels-Vishne, and then present a generalized approach to treat all “decent adjacency operators” at the same time. This will include an Alon-Boppana-like theorem, generalizing several known similar theorems. I will further claim a result that the Ramanujan complexes of Lubotzky-Samuels-Vishne have optimal spectrum with respect to any “decent adjacency operator”.

March 19

“Incidences of points and planes in three dimensions

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

March 6

On Schur’s conjecture

Andrey Kupavskii

A graph G=(V,E) is a diameter graph in R^d if the set of vertices V is a finite subset of R^d and the set of edges E is formed by pairs of vertices that are at diameter apart. In this talk we present the proof of Schur’s conjecture which states that a diameter graph on n vertices in R^d can have at most n d-cliques.