Working group algebra and combinatorics

The goal of this talk is to advertise a beautiful, infinite-dimensional algebraic variety known as Sato's Grassmannian, as well as its relation to realisable matroids and the Geelen-Gerards-Whittle matroid minor programme. Specifically, I will propose the conjecture that Sato's Grassmannian, with its Zariski topology, is Noetherian modulo the infinite symmetric group. Over a finite field F, this conjecture is equivalent to (a strong form of) the conjecture that realisable matroids over F are well-quasi-ordered with the minor order. Interestingly, unlike the matroid minor conjecture, our Noetherianity conjecture also makes sense over infinite fields.

Szegedy [1] showed that the partition function of any vertex coloring model is equal to the partition function of a complex edge coloring model. Using some fundamental results in geometric invariant theory, we characterize for which real vertex coloring model the edge coloring model can be taken to be real valued that is, we characterize which partition functions of real vertex coloring models are edge reflection positive. This answers a question posed by Szegedy [1].

[1] B. Szegedy, Edge coloring models and reflection positivity, Journal of the American Mathematical Society 20, 969–988, 2007.

A basic problem in Commutative Algebra asks one to compute the least number of polynomials needed to generate the toric ideal up to radical. This number is commonly known as the arithmetical rank of a toric ideal. A usual approach to this problem is to restrict to a certain class of polynomials and ask how many polynomials from this class can generate the toric ideal up to radical. Restricting the polynomials to the class of binomials we arrive at the notion of the binomial arithmetical rank of a toric ideal.

In the talk we study the binomial arithmetical rank of the toric ideal I_G of a finite graph G in two cases:

• G is bipartite,
• I_G is generated by quadratic binomials.

In the recent preprint arXiv:1210.0198 Hauenstein, Rodriguez, and Sturmfels discovered a conjectural bijection between critical points of the likelihood function on the complex manifold of matrices of rank r and cricital points on the complex manifold of matrices of co-rank r-1. I will discuss a proof of that conjecture for rectangular matrices and symmetric matrices.

Joint work with Marina Arav, Frank Hall, and Zhongshan Li.

A signed graph is a pair $(G,\Sigma)$ where $G$ is an undirected graph (in which parallel edges are permitted but loops are not) and $\Sigma \subseteq E(G)$. The edges in $\Sigma$ are called odd and the other edges are called even. A cycle of $G$ is called odd if it has an odd number of odd edges. If $U\subseteq V(G)$, then re-signing $(G,\Sigma)$ on $U$ gives the signed graph $(G,\Sigma\Delta \delta(U))$. A signed graph is a minor of $(G,\Sigma)$ if it comes from $(G,\Sigma)$ by a series of re-signing, deletions of edges and isolated vertices, and contractions of even edges.

If $(G,\Sigma)$ is a signed graph with $n$ vertices, $S(G,\Sigma)$ is the set of all symmetric $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j} > 0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j} < 0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}\in \mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i$ and $j$ are not connected by any edges, and $a_{i,i} \in \mathbb{R}$ for all vertices $i$. The stable inertia set, $I_s(G,\Sigma)$, of a signed graph $(G,\Sigma)$ is the set of all pairs $(p,q)$ such that there exists a matrix $A\in S(G,\Sigma)$ that has the Strong Arnold Hypothesis, and $p$ positive and $q$ negative eigenvalues. The stable inertia set of a signed graph forms a generalization of $\mu(G)$, $\nu(G)$ (introduced by Colin de Verdi\`ere), and $\xi(G)$ (introduced by Barioli, Fallat, and Hogben).

A specialization of $I_s(G,\Sigma)$ is $\nu(G,\Sigma)$, which is defined as the maximum of the nullities of positive definite matrices $A\in S(G,\Sigma)$ that have the Strong Arnold Hypothesis. This invariant is closed under taking minors, and characterizes signed graphs with no odd cycles as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 1$, and signed graphs with no odd-$K_4$- and no odd-$K^2_3$-minor as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 2$. In this talk we will discuss $I_s(G,\Sigma)$, $\nu(G,\Sigma)$ and these characterizations.

Joint work with Marina Arav, Frank Hall, and Zhongshan Li.

In this talk I will present the results in our recent paper "On the number of matroids" (http://arxiv.org/abs/1206.6270), in which we consider the problem of upper bounding the number of matroids on a ground set of size n. The talk will consist of two parts. In the first part, we describe a method for counting the number of stable sets in a regular graph. This method is interesting in itself.

In the second part, we use this method, in combination with some properties of the non-bases of a matroid, to give a compressed representation for matroids. This compressed representation then gives a new upper bound on the number of matroids.

Joint work with Nikhil Bansal and Rudi Pendavingh.

Robust network design considers the problem of designing a minimum-cost network to support some given set of demand patterns. This can be used to model the variability of traffic across a network. Particularly well studied in this context is the VPN problem: for each node, there is a specified upper bound on the total traffic to or from that node. The "VPN Conjecture" stated that there is always an optimal solution in the form of a tree; with Navin Goyal and Bruce Shepherd, we resolved this affirmatively. However, a very natural generalization remains open. Roughly speaking, the idea is to require that the network support all demands that can be routed on some given capacitated tree; if the tree is a star, the VPN problem is recovered. We propose a specific polynomial time algorithm, which we conjecture always returns an optimal solution.

In this talk, I will discuss a new simplification of the proof of the VPN Conjecture, and how this leads to some progress on the generalization. T-joins will play the starring role.

(Includes joint work Navin Goyal and Bruce Shepherd, and Michel Goemans, Yusuke Kobayashi and Rico Zenklusen).

The hyperbolicity cones associated with the elementary symmetric polynomials provide an intriguing family of non-polyhedral relaxations of the non-negative orthant which preserve its low-dimensional faces and successively discard higher dimensional facial structure.

We show by a simple and explicit construction that this family of convex cones (as well as their analogues for symmetric matrices) have polynomial-sized representations as projections of slices of the PSD cone. This, for example, allows us to solve the associated linear cone program using semidefinite programming, and give corresponding explicit semidefinite representations for the (poorly understood) duals of these cones.

(Based on joint work with Pablo Parrilo)

Arxiv link: http://arxiv.org/abs/1208.1443

The main aim is to give an introduction to the various structural and probabilistic approaches to a notorious conjecture of Erdös and Hajnal, which is concerned with understanding how the exclusion from G of a fixed graph H as an induced subgraph affects the maximum size of a homogenous set (a clique or stable set) in G.

This area of extremal graph theory is closely related to Ramsey theory, random graphs and structural graph theory. Some of the talk will be devoted to describing some recent asymptotic formulations of the conjecture, proved using Szemerédi regularity (one of which is joint work with McDiarmid, Reed and Scott).

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.

Consider a graph G whose vertex set is a separable probability space V and whose edge set E is a measurable subset of V xV. We say that a measurable subset S of V is almost independent if the set of all edges with both endpoints in S has measure zero, and we ask for the largest possible measure of an almost independent set. In our approach to this question we develop a suitable generalization of the Lovász-theta function for finite graphs to get an upper bound on this measure.

(Joint work with Frank Vallentin.)

Let G be an undirected graph with n nodes. Let S(G) be the set of all (n x n) real symmetric, positive definite matrices with zeros corresponding to non-edges of G. We describe the stabilizer of S(G) in GL_n(R) of the model, in the natural action of GL_n(R) on symmetric matrices.

The main motivation for this work is in statistics, where S(G) is identified with the graphical Gaussian model on G. Our results have important consequences for the study of the maximum likelihood inference for this model class.

This is a joint work with Jan Draisma and Sonja Kuhnt.

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.

In 1957, Hirsch conjectured that the graph of a $d$-dimensional polyhedron with $n$ facets cannot have diameter greater than $n-d$. After stating the problem, we survey the positive and negative sides of the conjecture.

For the positive side, Barnette and Larman showed that the diameter of polyhedra is linear in fixed dimension. Kalai and Kleitman proved a subexponential bound on the diameters of polyhedra. Their subexponential bound holds on a larger class of combinatorial objects which has become the centerpiece of a recent online collaborative project. We also present our work diameter bounds on transportation polytopes, a quadratic upper bound on the diameter of a certain class of $3$-way transportation polytope (joint work with De Loera, Onn, and Santos) and a proof of the Hirsch Conjecture for a certain class of $2$-way transportation polytope.

For the negative side, we first describe values for $(n,d)$ where Hirsch-tight polytopes are known to exist and prove an analogous result for transportation polytopes. We will discuss three variants of the Hirsch Conjecture: unbounded, monotone, and topological. We close with the recent breakthrough result of Santos where he constructs a polytope that violates the Hirsch Conjecture.

There has recently been ample interest in the question of which sets can be represented by linear matrix inequalities (LMIs). A necessary condition is that the set is rigidly convex, and it has been conjectured that rigid convexity is also sufficient. To this end Helton and Vinnikov conjectured that any real zero polynomial admits a determinantal representation with symmetric matrices.

Petter Brändén disproved recently this conjecture. By relating the question of finding LMI representations to the problem of determining whether a polymatroid is representable over the complex numbers, he finds a real zero polynomial such that no power of it admits a determinantal representation. The proof uses recent results of Wagner and Wei on matroids with the half-plane property, and the polymatroids associated to hyperbolic polynomials introduced by Gurvits.

I will try to present the main steps of the proof.

Tensor rank generalises matrix rank to higher-dimensional blocks of numbers, but is much harder to get a grip on, both computationally and theoretically. For instance, while a rank-k matrix cannot be approximated by matrices of rank k-1, some rank-k tensors _can_ be approximated by tensors of rank k-1. They are then said to have "border rank" at most k-1. I will sketch a proof of a recent theorem which says that tensors of border rank at most k can be defined by the vanishing of polynomials whose degrees do not exceed some bound d(k), which is uniform in that it does not depend on the sizes of the tensor, nor even on the number of factors (dimension) in the tensor.

Our proof only yields the _existence_ of d(k), not an explicit value. Known facts are d(0)=1 (trivial), d(1)=2 (classical), d(2)=3 (Landsberg-Manivel-Weyman), d(k)>=k+1 (not so difficult), d(4)>=9 (Strassen).

Like tree width in graphs, branch width is a central concept in matroid structure theory. When the branch width of the matroids in a class is low, questions surrounding well-quasi-ordering and efficiency of algorithms become more tractable. When the branch width of a matroid is high, different good things happen. For instance, the matroid will have the cycle matroid of a big grid as minor. We will look at another consequence of high branch width: an extension of the Splitter Theorem.

Based on joint work with Jim Geelen.

Metric graphs can be regarded as combinatorial analogues of algebraic curves (or, equivalently, Riemann surfaces). I will explain how the beautiful combinatorics of a certain game on metric graphs implies a difficult theorem, due to Griffiths and Harris in the 1980s, about algebraic curves; and how, vice verse, a theorem by Kleiman and Laksov from the 1970s concerning curves implies a strong result about the aforementioned game.

(Joint work with Filip Cools, Sam Payne, and Elina Robeva.)