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 – IMEUSP
Date  Time  Activity 

November 11 (Tuesday)  9:30–10:00  Group presentations 
10:00–11:00  The ErdősHajnal conjecture Stéphan Thomassé, ENS de Lyon 

11:00–11:15  Coffee Break  
11:15–12:15  Extremal problems for random discrete structures Yoshiharu Kohayakawa, USP 

12:15–14:30  Lunch  
14:30–15:30  Complexity and decomposition to the set of factors Svetlana Puzynina, ENS de Lyon 

15:30–16:30  Optimization methods for packing problems Fernando Mario de Oliveira Filho, USP 

16:30–xx:xx  Coffee and discussions  
November 12 (Wednesday)  10:00–11:00  Communication complexity and extended formulations of polytopes Aurélie Lagoutte, ENS de Lyon 
11:00–11:15  Coffee Break  
11:15–12:15  Vertices of theta bodies in matrix space Marcel Silva, USP 

12:15–19:00  Lunch and events from the global tracks  
November 13 (Thursday)  10:00–11:00  Decomposition of highly connected graphs into paths of length five Guilherme Mota, USP 
11:00–11:15  Coffee Break  
11:15–12:15  The Permanent and the Newton Polygon: a story about the difficulty of computing a polynomial Natacha Portier, ENS de Lyon 

12:15–14:30  Lunch  
14:30–xx:xx  Discussions 
Abstracts of the Talks

The ErdősHajnal conjecture
Stéphan Thomassé, ENS de LyonAbstract: 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ősHajnal 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 EHconjecture, 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, USPAbstract: 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 LyonAbstract: 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^{k1})\), this inclusion is strict for \(k \geq 2\).

Optimization methods for packing problems
Fernando Mario de Oliveira Filho, USPAbstract: 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 spherepacking 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 3dimensional 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 LyonAbstract: 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 superpolynomial 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 nondeterministic protocol whether \(K\) intersects \(S\) or not. A certificate for the nonintersection 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 CliqueStable 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 CliqueStable 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 ErdosHajnal property
 in P5free graphs
 in perfect graphs with no balanced skew partition.

Vertices of theta bodies in matrix space
Marcel Silva, USPAbstract: 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 fulldimensional. In this talk, we discuss the following result: the vertices of the lifted theta body of a graph \(G\) are precisely the symmetric rankone 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 LyonAbstract: 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, USPAbstract: 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\)edgeconnected 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.