Working group

  algebra and combinatorics

Ternary sextics and quaternary quartics are the smallest cases where there exist nonnegative polynomials that are not sums of squares (SOS). A complete classification of the difference between these cones was given by G. Blekherman via analyzing the corresponding dual cones. An exact computation of the extreme rays in order to separate a fixed nonnegative polynomial that is not SOS is difficult. We provide a method substantially simplifying this exact computation for certain classes of polynomials on the boundary of the PSD cones. In particular, our method yields separating extreme rays for almost every nonnegative ternary sextic with at least seven zeros. As an application to further instances, we compute a rational certificate proving that the Motzkin polynomial is not SOS.

The reformulation-linearization technique (RLT), introduced by Adams, H.D. Sherali, provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems.

We show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints.

Joint work with Etienne de Klerk, Renata Sotirov and Uwe Truetsch

In this talk we prove (possible a few versions of) the Szemerédi Regularity Lemma and use it to deepen our understanding of the theory of graph limits by investigating the proofs of some of the basic propositions in this theory.

In particular we take a closer look at why the set of graphons is compact in the topology induced by the cut metric. (For those interested, this happens to be one of the theorems that makes Razborov's flag algebra theory work.)

The material for the talk will come primarily from various articles of Lovász and Szegedy.

The chromatic number is defined for bounded, symmetric operators by extending the definition for the adjacency matrix of finite graphs. The knowledge of the spectrum of the operator gives lower bounds. This provides a theoretical framework in which many coloring problems for finite and infinite graphs can be conveniently studied with the help of harmonic analysis and convex optimization. The theory is applied to infinite graphs on Euclidean space and on the unit sphere, thereby several results from Fernando's thesis will be derived and generalized.

This talk contains a conjecture by Johan van Leeuwaarden and Niek Bouman (both TU/e) on energy-minimising configurations of particles on a two-dimensional toric grid, a systematic approach to a generalisation of their conjecture, and a proof of an other special case of that generalisation, namely, 2^n-1 particles on the n-dimensional Hamming cube.

Several open problems remain, and input is welcome.

Joint work with Johan and Niek.

Given a graph G=([n],E) its Gram dimension is the smallest integer k >= 1 with the following property:
for any choice of vectors q₁,..,q_n in R^d there exist vectors p₁,..,p_n in R^k such that ||q_i||=||p_i|| and q_i^Tq_j=p_i^Tp_j, for all ij in E.

The class of graphs with Gram dimension less than r, denoted by G_r, is minor closed. Clearly K_r+1 is a forbidden minor for membership in G_r. In fact, this is the only forbidden minor for r <= 3. For r=4 we show that the only minimal forbidden minors are K₅ and K_2,2,2.

These results are closely related with the results of Belk and Connelly concerning the class of k-realizable graphs. A graph is called k-realizable if for any choice of vectors q₁,..,q_n in R^d there exist vectors p₁,..,p_n in R^k such that ||q_i - q_j||=||p_i - p_j||, for all ij in E. In the talk I will elaborate on the similarities and differences between the two settings.

Based on joint work with Monique Laurent.

I will discuss the irreducible representations of the Euclidean motion group and how they are used to obtain the Fourier inversion formula for functions defined over the motion group.

We discuss a notion of limit for graphs, first studied just a few years ago by László Lovász, Balázs Szegedy, and others. The discussion will include giving a metric for the set of all graphs, which is applicable in the study of extremely large graphs. We'll explore Cauchy-ness in this metric, and define a class of limit objects that will make our new metric space complete.

In this talk, I will present some preliminary work on the quantum capacity of a graph, a natural extension of the Shannon capacity which arises in a setting where communication across a noisy classical channel is aided by the use of entanglement. We exhibit a simple collection of graphs for which the quantum capacity is strictly greater than the Shannon capacity, adding to examples found by Leung et al. (2010).

See paper of Beigi for a proof that the Lovász theta number is an upper bound.

(Joint work with Harry Buhrman.)

Little is known in general about the integrality gap of SDP relaxations of high order. Some recent work of Karlin, Mathieu and Nguyen (IPCO, 2011) shows that the integrality gap of the Lasserre hierarchy decreases quickly with the order t of the relaxation, namely, as t/(t-1). The authors also show that this property does not hold for the Sherali-Adams hierarchy.

A spin network is a labeled graph together with a simple combinatorial procedure for evaluating it, which yields an integer. Such evaluations of graphs are called spin networks because they are abstract versions of calculations that are commonly performed in quantum mechanics. The challenge is to understand how the evaluations of a fixed graph G behave when the labels get larger and larger. In special cases the growth rate of the evaluations encodes geometrical features such as lengths and angles of realizations of the graph G as a three-dimensional Euclidean polytope.

In this talk I will present a generating function for all the spin network evaluations of an arbitrary fixed graph G and how this can be used to prove the existence of an asymptotic expansion. Given time I will also describe a system of recursions satisfied by the evaluations of G and how these can be turned into equations satisfied by the dihedral angles of a certain polytope.

In this talk I will give a characterization of the rank of an edge connection matrix of a partition function of a (real) vertex model.

The rank is equal to the dimension of a homogeneous component of a tensor subalgebra which is the invariant algebra of a subgroup of the orthogonal group. The subgroup is completely determined by the vertex model.

The result is analogous to a result of L. Lovász characterizing the ranks of vertex connection matrices of partition functions of real weighted spin models.

This result answers a question of B. Szegedy.

Given a graph G=([n],E), let E(G) denote the elliptope of G, i.e., the set of vectors x in R^E for which there exists an n-dimensional psd matrix X with diagonal 1 (correlation matrix), such that x_ij=X_i,j, for every edge ij. Additionally, let CUT(G) denote the cut polytope of a graph G, in +1,-1 variables. It is easy to verify, that for any graph G, CUT(G) is contained in E(G). The smallest K>0 such that E(G) is contained in K x CUT(G), is denoted by K(G), and is known as the Grothedieck constant of G.

The main goal of the talk is to exhibit a formula for the Grothendieck constant of a graph G with no K₅ minor, in terms of its girth (minimum length of a cycle in G). As a consequence, the Grothendieck constant for K₅-minor free graphs, can be computed in polynomial time. To get to this result, we first establish a similar formula for the Grothedieck constant of a circuit, C_n, in terms of n.

Additionally, I will discuss some preliminary results concerning the following generalization of the classical Grothendieck constant K(G). Let E_r(G) denote the convex hull of correlation matrices of rank at most r. It is easy to see that E_r(G) is contained in E(G). The smallest K>0 such that E(G) is contained in K x E_r(G), is denoted by K(r,G), and is called the rank r Grothendieck constant of G. My intention is to sketch the proof of the fact that K(r,C_n)=1 for r at least 2.

Joint work with M. Laurent

Based on the work of Ellis, Filmus and Friedgut:
Triangle-intersecting Families of Graphs

The main result is a proof of a conjecture by Simonovits and Sós from 1976 that is related to the Erdös-Ko-Rado theorem.

Let E be the edge set of the complete graph on n vertices. The conjecture states that the maximum number of subsets of E that pairwise share a triangle, is equal to the obvious lower bound of (n\choose 2)/8. Furthermore, every optimal solution consists of all subsets containing a fixed triangle.

Based on the work of Ahmadi, Olshevsky, Parrilo and Tsitsiklis:
NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

The main result is that unless P=NP there is no polynomial time algorithm to decide whether a multivariate polynomial of degree 4 is convex, thus resolving an open question posed by Shor in 1982. The proof relies on two ingredients:

• an earlier result showing that testing nonnegativity of a biquadratic form is NP-hard (there is a nice simple reduction from the stable set problem via Motzkin-Straus theorem),
• an ingenious (yet relatively simple) construction relating Hessians of convex polynomials with general biquadratic forms.

I will show that the maximum density of a set of points in a metric space M having no two points at distances d_1 << ... << d_N decays exponentially with N, as long as the distances are chosen to be far away from each other. This holds for many different metric spaces M; in this talk I will discuss the case in which M is a compact, connected, rank-one symmetric space, like the sphere or the real projective space.