November 11 and 12, 2014

Auditorium of NUMEC (Núcleo de Apoio à Pesquisa em Modelagem Estocástica e Complexidade)
at the Institute of Mathematics and Statistics of the University of São Paulo – IME-USP

Abstracts of the Talks

• The Erdős-Hajnal conjecture
  Stéphan Thomassé, ENS de Lyon

  Abstract: Random graphs in \(G(n,p)\) typically have maximum cliques and stable sets of size \(O(\log n)\). More generally, they induce all possible graphs on \(O(\log n)\) vertices. A natural question, raised by Erdős and Hajnal, is to ask for the maximum size of a stable set or clique in a graph \(G\) on \(n\) vertices not inducing a fixed graph \(H\).

  More precisely, the Erdős-Hajnal conjecture asserts that for every \(H\), there is a constant \(c\) such that every \(H\)-free graph has a clique or a stable set of size at least \(n^c\).

  This surprisingly large jump from logarithmic size to polynomial size has been confirmed for few particular graphs \(H\), but remains open even for the path or the cycle of length 5.

  In this talk, I will review some results about EH-conjecture, make some link with some other classical problems involving cliques and stable sets, and finally sketch a proof when forbidding an induced path of length \(k\) and its complement.

  This is joint work with Marthe Bonamy, Nicolas Bousquet and Aurélie Lagoutte.

• Extremal problems for random discrete structures
  Yoshiharu Kohayakawa, USP

  Abstract: We discuss some extremal problems and results in the area of probabilistic combinatorics, including Turán type problems for random graphs and problems from additive combinatorics. The main the aim of the talk will be to motivate this general line of research. The more technical parts of the talk will focus on what are known as degenerate problems.

• Complexity and decomposition to the set of factors
  Svetlana Puzynina, ENS de Lyon

  Abstract: In this talk we introduce a new hierarchy of classes of languages and infinite words and its connection with complexity classes. Namely, we say that a language belongs to the class \(L_k\) if each word in it can be introduced as a catenation of \(k\) words from a language \(S\), such that the number of words of length \(n\) in \(S\) is bounded by a constant. The class of infinite words whose set of factors is in \(L_k\) is denoted by \(W_k\). In this talk we focus on the relations between the classes \(W_k\) and the subword complexity of infinite words, which is as usual defined as the number of factors of the word of length \(n\). In particular, we prove that the class \(W_k\) coincides with the class of infinite words of linear complexity. On the other hand, although the class \(W_k\) is included in the class of words of complexity \(O(n^{k-1})\), this inclusion is strict for \(k \geq 2\).

• Optimization methods for packing problems
  Fernando Mario de Oliveira Filho, USP

  Abstract: Some of the most interesting and difficult problems in geometry are packing problems, which basically ask the question: how much of a certain space can be filled by nonoverlapping copies of given objects?

  The most famous example is perhaps the sphere-packing problem: we wish to fill as much as possible of Euclidean space with nonoverlapping copies of the unit ball.

  Another example with a rich history going back to Aristotle is the tetrahedra packing problem: how much of R^3 can we fill with congruent, nonoverlapping copies of a given regular tetrahedron? A related problem, which can be seen as a packing problem in the compact space SO(3) of 3-dimensional rotations, is the following: how many nonoverlapping regular tetrahedra can have a vertex in common?

  In packing problems, lower bounds for the maximum packing density are found by constructions, i.e., by showing dense packings. Finding upper bounds is a nonconstructive effort, and there are many techniques that have been explored to prove upper bounds. In this talk, I will discuss a unified approach for the computation of upper bounds. This approach is an extension of the Lovász theta number, a graph parameter that provides an upper bound, based on semidefinite programming, to the independence number of a finite graph, together with ideas from harmonic analysis. I will show how the approach applies to packings of congruent copies of a given convex body in Euclidean space and also how it applies to some interesting packing problems in compact spaces, like the packing problem on SO(3) mentioned above.

  (Joint work with Frank Vallentin.)

• Communication complexity and extended formulations of polytopes
  Aurélie Lagoutte, ENS de Lyon

  Abstract: The concept of extended formulations of polytopes was introduced by Yannakakis in 1991 in his seminal paper «Expressing Combinatorial Optimization Problems by Linear Programs». A polytope \(P\) has a small extended formulation if it is the projection of a polytope \(Q\) lying in a higher dimensional space, with a small number of facets. In particular, he studies the stable set polytope and focus on the perfect graphs case, where it can be fully described with the clique constraints. He then asked whether the stable set polytope in this case admits a polynomial (in the number of vertices) extended formulation (which he proves for comparability graphs), or if one can find a super-polynomial lower bound.

  In this second perspective, he highlights a lower bound stated as a communication complexity problem: Alice is given a clique \(K\), Bob is given a stable set \(S\), and they have to decide via a non-deterministic protocol whether \(K\) intersects \(S\) or not. A certificate for the non-intersection is a bipartition of the vertices such that \(K\) is included in one side, and \(S\) is included in the other side. A set of certificates which contains every useful certificates is called a Clique-Stable Set separator, and the goal is to find such a set with a polynomial number of bipartitions. The question is open in general, and Yannakakis’ question (that is, on perfect graphs) is still also open. The best lower bound so far is \(\Omega(n^{2-\epsilon})\) and the best upper bound is \(O(n^{\log n})\).

  We prove that such a polynomial Clique-Stable set separator exists

  • in random graphs,
  • in \(H\)-free graphs where \(H\) is a split graph (which generalize Yannakakis’ result on comparability graphs),
  • in graphs with no induced path on \(k\) vertices and its complement, and we make some connections with the Erdos-Hajnal property
  • in P5-free graphs
  • in perfect graphs with no balanced skew partition.

• Vertices of theta bodies in matrix space
  Marcel Silva, USP

  Abstract: The theta body of a graph is one of the most elegant tractable relaxations of the stable set polytope. Key to its tractability is the fact that the theta body can be represented as the projection of a spectrahedron, that is, as the projection of the feasible region of a semidefinite program. We are interested in the boundary structure of such spectrahedron, which we call the lifted theta body of the graph. This study may be seen as an analogue of polyhedral combinatorics in the context of semidefinite programs.

  Spectrahedra may have infinitely many extreme points due to nonlinearity. A special class of such extreme points are the vertices of the convex set, i.e., those extreme points whose corresponding normal cones are full-dimensional. In this talk, we discuss the following result: the vertices of the lifted theta body of a graph \(G\) are precisely the symmetric rank-one tensors of incidence vectors of stable sets of \(G\).

  (Joint work with Levent Tunçel.)

• The Permanent and the Newton Polygon: a story about the difficulty of computing a polynomial
  Natacha Portier, ENS de Lyon

  Abstract: The Permanent is almost a twin brother to the Determinant, but it is believed to be much more difficult to compute. Actually, it plays the role for the algebraic complexity classes VP and VNP that the problem SAT plays for the complexity classes P and NP. In this talk, I will present a new line of work to try to prove that the Permanent is hard to compute, using the newton polygon of bivariates polynomials.

• Decomposition of highly connected graphs into paths of length five
  Guilherme Mota, USP

  Abstract: We study the Decomposition Conjecture posed by Barát and Thomassen (2006), which states that for every tree \(T\) there exists a natural number \(k_T\) such that, if \(G\) is a \(k_T\)-edge-connected graph and \(|E(T)|\) divides \(|E(G)|\), then \(G\) admits a decomposition into copies of \(T\). This conjecture was verified for stars, some bistars, paths whose length is a power of 2, and paths of length 3. In this paper we verify the Decomposition Conjecture for paths of length 5.

  (Joint work with Fabio Botler, Márcio Oshiro and Yoshiko Wakabayashi.)

Acknowledgements

We gratefully acknowledge the sponsorship from Université de Lyon and Universidade de São Paulo, as well as the support of MaCLinC and NUMEC for hosting this event.