Computational Algebra & Geometry PhD position

Communicated by Rudi Pendavingh

The Department of Mathematics and Computer science at Eindhoven University in the Netherlands has a vacancy for a PhD position in Computational Algebra and Geometry.

The subject of the PhD project will be decided based on the preferences of the best candidate, who will be allowed choose from several projects defined by Jan Draisma, Hans Cuypers, and Rudi Pendavingh.

One possible project is `Algebraic Matroids in Sage’, under the daily supervision of Rudi Pendavingh.

PhD positions in the Netherlands take 4 years and are regular, albeit temporary, paid jobs.

Please send your inquiries to Rudi Pendavingh (rudi.pendavingh@gmail.com).

Matroids and graphs in Princeton

All the contributors to this blog have been in Princeton, New Jersey within the last few weeks for the 2014 International Workshop on Structure in Graphs and Matroids. This meeting is a descendant of three very successful workshops run by Bert Gerards in Sittard and Maastricht between 2008 and 2012. Although the location has shifted from the Netherlands to the US, a Dutch connection remains, since the 2014 workshop was organised by Rudi Pendavingh and Stefan van Zwam. They both deserve a vote of thanks, for doing a great job and for continuing the tradition; the biennial meeting has become one of the most important fixtures for people interested in the structural theory of matroids and graphs.

In this type of post, I would usually make note of talks that were relevant to the contents of this blog, as well as talks that I found particularly interesting or attractive. That rule is pretty much useless in this case. For obvious reasons, all the talks had connections to matroid theory, and a large number of talks were high-quality presentations about high-quality results. Judging by a number of conversations I have had over the years, there is a feeling that the matroid community (and its relatives) does a better-than-average job of mathematical communication. I don’t think you would have seen much to contradict that belief at this workshop.

It seems as though it has been a good couple of years for matroid and graph research, since a number of people spoke about important new developments, but one such development obviously stands out. Rota’s Conjecture was the outstanding open problem in matroid theory for decades, and its resolution by Jim Geelen, Bert Gerards, and Geoff Whittle is certainly the most significant accomplishment in the field. Geoff gave a talk on one important step in that project. In particular, he talked us through a sketch of the proof that an excluded minor for representability over a finite field must be $f$-connected. That is, if $\mathrm{GF}(q)$ is a finite field, then for every positive integer $k$, there is an integer $n_{q}(k)$ such that whenever $M$ is an excluded minor for $\mathrm{GF}(q)$-representability, and $(A,B)$ is a $k$-separation of $M$, then either $|A|\leq n_{q}(k)$ or $|B|\leq n_{q}(k)$.

Geoff’s talk is complemented by an article in the Notices of the American Mathematical Society. In addition, you can find the slides from many of the conference talks on this page.

Although singling out talks is essentially an impossible task, I will just mention one that I found particularly interesting. Reinhard Diestel reported on work with Sang-Il Oum that provides a meta-theorem about various width parameters. I’ll illustrate the theorem by talking about branch-width and tangles. A branch-decomposition of a matroid or graph is a tree where the non-leaf vertices have degree three, and the leaves are labeled with elements of the ground-set (edge-set). Now each edge of the tree represents a partition of the ground-set into two parts, in other words, a separation. The decomposition has low width if each of those separations has low order. If a matroid does not have low-width branch-decomposition, then we should be able to certify that this is the case. Tangles allow us to do so. A tangle is an orientation of each of the separations of low order. In particular, if we have a tangle, then we have designated a “small” side of each low-order separation. Certain constraints must be satisfied in order for this orientation to be sensible. The most important of these constraints is that three small sides should not cover the entire ground-set between them. Note that in a low-order decomposition, each internal vertex represents a partition of the ground-set into three “small” parts, so a decomposition is a certificate that there can be no tangle, and vice versa. The work by Diestel and Oum generalises these ideas. We choose families of separations, for example the families that might be represented by an internal vertex of a decomposition, and then the theorem guarantees that either there will be a labeled tree where the internal nodes represent members of our chosen families of separations, or else there is some consistent orientation of separations that avoids those families. More details can be found on the arxiv.

At the close of the conference, Stefan extended an invitation to those interested in contributing to this blog, which I will repeat here. If you have an idea for a post, then please get in touch with one of us to discuss it.

Much speculation surrounds the location of the next workshop, two years from now, and multiple suggestions have been made. Expect updates to follow.

A conference in honour of Chris Godsil

I spent last week in Waterloo (Ontario) attending a conference celebrating the work of Chris Godsil (and his 65th birthday). It was a week packed with excellent talks, mostly by current or former students and collaborators of Chris.

The conference title is a clear indication of the breadth of Chris’ work: “Algebraic combinatorics: spectral graph theory, Erdös-Ko-Rado theorems and quantum information theory”. The number of talks shows the impact of Chris Godsil’s research. There were way too many speakers for me to even mention all of them, so I’ll just talk about a few of the talks.

The conference opened with Brendan McKay, who talked about counting edge-coloured regular graphs. In the 1980s, together with Chris Godsil, the speaker had determined an asymptotic formula for counting edge-coloured regular bipartite graphs (which correspond to latin rectangles). This result suggested investigating the analogous problem for general edge-coloured regular graphs, which was the subject of the talk.

On the same day the only talk to mention matroids was delivered by Gordon Royle. He talked about roots of the chromatic polynomial of graphs and matroids. The chromatic polynomial of a graph is a polynomial that counts the number of proper colouring of the vertices of the graph with a certain number of colours. I won’t get into any details, you can find a small introduction to the chromatic polynomial on wikipedia . Despite being studied by mathematicians and physicists for a long time, there are many open questions about the chromatic polynomial of graphs, in particular about the location of its real and complex roots. Being an evaluation of the Tutte polynomial, the chromatic polynomial can easily be defined for matroids (although in this case it’s usually called characteristic polynomial). Almost nothing is known about the location of the roots of the chromatic polynomial of matroids, except for results on graphic matroids and cographic matroids (the chromatic polynomial of a cographic matroid is the flow polynomial of the associated graph). I will soon start a project with Gordon on this intriguing subject; hopefully this will lead to some posts about this.

Cheryl Praeger was also part of the small delegation from the University of Western Australia; she gave a history of the classification of finite 2-transitive permutation groups and its applications.

Peter Cameron talked about endomorphisms and synchronisation; every graph has a semigroup of endomorphisms, but one can also start from a transformation semigroup and construct a graph with nice properties.

Chris Godsil’s talk concerned the last part of the conference title, quantum information theory. He talked about a range of tools to obtain graph which have uniform mixing in quantum walks. Coding theory, association schemes and number theory all figured in his talk. Chris lived to his reputation of being an avid photographer by taking pictures of all the speakers at the conference. An email front he organisers, on the day before his talk, suggested that we all took pictures of him during his talk (more precisely, during the 5th slide). I didn’t do a very good job with my picture, but here it is anyway.

photo

The conference closed with a talk by Karen Meagher, who was a post-doc at the University of Waterloo working with Chris Godsil. She talked about an algebraic perspective on Erdös-Ko-Rado theorems. The EKR-theorem gives the exact structure of the largest collection of k-subsets of n elements with the property that every two sets share at least one element. This type of question can be extended to many combinatorial objects. This is the topic of a book that Karen is writing with Chris. Quoting her abstract, the book is “$\epsilon$ away from completion”; I look forward to see it published.

Seymour’s 1-flowing conjecture II

In the last post, we had just reached the definition of a 1-flowing matroid. To recap, let $M$ be a matroid on the groundset $E$, and let $e$ be an element of $E$. We choose a function that assigns a positive integral capacity, $c_{x}$, to each element $x\in E-e$. A flow is a function that assigns a non-negative real number, $f_{C}$, to each circuit, $C$, containing $e$. We insist that, for every $x\in E-e$, the inequality $\sum f_{C}\leq c_{x}$ holds (here the sum is taken over all circuits that contains $e$ and $x$). The value of a flow is $\sum f_{C}$, where the sum is taken over all circuits that contain $e$. In the last post, the following inequality was an exercise.

$\text{maximum value of a flow} \leq \min\{\sum_{x\in C^{*}-e}c_{x}\}$

(the minimum is taken over all cocircuits $C^{*}$ such that $e\in C^{*}$).

Proof. Let $C^{*}$ be an arbitrary cocircuit that contains $e$. Let $\mathcal{C}$ be the collection of circuits that contain $e$. Let $\mathcal{D}$ be the collection of all ordered pairs $(x,C)$ where $x$ is an element in $C^{*}-e$, and $C$ is a circuit that contains $\{e,x\}$. Since a circuit and a cocircuit cannot intersect in $\{e\}$, it follows that every circuit in $\mathcal{C}$ appears in an ordered pair in $\mathcal{D}$. Therefore

\[
\qquad\sum_{C\in\mathcal{C}}f_{C}\leq\sum_{(x,C)\in\mathcal{D}}f_{C}
=\sum_{x\in C^{*}-e}\sum_{C\in\mathcal{C}\colon x\in C}f_{C}
\leq \sum_{x\in C^{*}-e}c_{x}\qquad\square
\]

We have shown that the value of a flow is bounded above by the capacity of a cut, for every matroid, every element $e$, and every choice of capacities. In some matroids, the inequality is actually an equality for every choice of capacities. In this case, we say that $M$ is $e$-flowing. If $M$ is $e$-flowing for every element $e$, then we say $M$ is $1$-flowing. This definition is motivated by min-max theorems in graph theory, such as the max-flow min-cut theorem. As detailed in the last post, these theorems show that graphic and cographic matroids are $1$-flowing. Seymour’s $1$-flowing conjecture concerns a characterisation of the $1$-flowing matroids.

Bertrand Guenin [Gue02] restates Seymour’s conjecture in a way that I initially did not understand. This method of talking about $1$-flowing matroids involves using ideas from linear programming. Say that $M$ is a matroid on the groundset $E$, and $e$ is an element of $E$. Let $\mathcal{C}$ be the collection of circuits that contain $e$. Let $A$ be the $0$-$1$ matrix whose columns are labelled by elements of $E-e$, and whose rows are labelled by the members of $\mathcal{C}$, where an entry $A_{C,x}$ is equal to one if and only if $x\in C$. Let $\mathcal{P}$ be the set of vectors, $\mathbf{x}$, in $\mathbb{R}^{E-e}$ such that every entry of $\mathbf{x}$ is non-negative, and every entry of $A\mathbf{x}$ is at least $1$. This is the intersection of several half-spaces in $\mathbb{R}^{E-e}$, so $\mathcal{P}$ is a polytope. Guenin’s statement of Seymour’s conjecture rests on the following fact:

Lemma 1. If $M$ is $e$-flowing, then the vertices of $\mathcal{P}$ have $0$-$1$ coordinates.

This wasn’t obvious to me, so I spent some time thinking about why it should be true. My relatively naive proof follows. A more sophisticated argument can be found in Cornuejols [Cor01].

If $\mathbf{a}$ and $\mathbf{b}$ are real vectors with the same number of entries, we write $\mathbf{a}\geq\mathbf{b}$ to mean that every entry of $\mathbf{a}$ is at least as large as the corresponding entry in $\mathbf{b}$. We write $\mathbf{0}$ and $\mathbf{1}$ for the vectors of all zeroes and the vector of all ones, and we use $\mathbb{R}_{\geq 0}$ to denote the set of non-negative reals. Let $\mathbf{c}$ be the vector in $\mathbb{Z}_{+}^{E-e}$ that contains the capacity of each element in $E-e$.

Proposition 1. The value of a maximum flow is equal to
\[
\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}.
\]

Proof. The vector $\mathbf{y}$ assigns a non-negative real value to each circuit containing $e$. The linear program maximises the sum of these values, while respecting the constraint that the sum of the values on circuits passing through an element of $E-e$ must be no greater than the capacity of that element. Thus the solution to the linear program is exactly the maximum value of a flow. $\square$

Proposition 2. The minimum of $\sum_{x\in C^{*}-e}c_{x}$ taken over all cocircuits, $C^{*}$, that contain $e$, is equal to
\[
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}.
\]

Proof. A circuit and a cocircuit cannot meet in a single element. Therefore, if $C^{*}$ is a cocircuit containing $e$, and $C$ is a member of $\mathcal{C}$, then $C^{*}-e$ and $C-e$ have a non-empty intersection. In other words, if $\mathbf{a},\mathbf{b}\in \{0,1\}^{E-e}$ are the characteristic vectors of $C-e$ and $C^{*}-e$ respectively, then $\mathbf{a}^{T}\cdot \mathbf{b} \geq 1$. Thus the dot product of $\mathbf{b}$ with any row of $A$ is at least one. This means that $A\mathbf{b} \geq \mathbf{1}$, so $\mathbf{b}$ is contained in $\{A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}$. Thus
\begin{multline*}
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}
\leq\\
\min\{\sum_{x\in C^{*}-e}c_{x}\colon C^{*}\ \text{is a cocircuit of}\ M,\ e\in C^{*}\}.
\end{multline*}

For the converse, assume $\mathbf{x}_{0}\in \{0,1\}^{E-e}$ is a solution to the program $\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}$. As the entries of $\mathbf{c}$ are non-negative, we can assume that there is no vector in $\{\mathbf{x}\in\{0,1\}^{E-e}\colon A\mathbf{x} \geq \mathbf{1}\}$ with support properly contained in the support of $\mathbf{x}_{0}$. Therefore $\mathbf{x}_{0}$ is the characteristic vector of a set $D\subseteq E-e$, where $D$ is minimal with respect to meeting every $C\in \mathcal{C}$. We will show that $D\cup e$ is a cocircuit of $M$. Suppose that $D\cup e$ is coindependent. Then there is a basis $B$ of $M$ that has an empty intersection with $D\cup e$. Now $B\cup e$ contains a circuit that contains $e$, and this circuit has an empty intersection with $D$. This is a contradiction, so $D\cup e$ contains a cocircuit $C^{*}$. Suppose that $e\notin C^{*}$, and let $c$ be an arbitrary element of $C^{*}$. By the minimality of $D$, there is a circuit $C \in\mathcal{C}$ such that $C$ has a non-empty intersection with $D$, but not with $D-c$. Then $C$ meets the cocircuit $C^{*}$ in a single element, $c$. This contradiction means that $e\in C^{*}$. As a circuit and a cocircuit cannot meet in a single element, every circuit in $\mathcal{C}$ meets $C^{*}-e\subseteq D$ in at least one element. The minimality of $D$ implies that $C^{*}-e=D$, so $D\cup e$ is a cocircuit, as desired. Now $\mathbf{c}^{T}\mathbf{x}_{0}$ is equal to $\sum_{x\in C^{*}-e}c_{x}$, and the proposition follows. $\square$

It follows from Propositions 1 and 2 that $M$ is $e$-flowing if and only if the two programs
\[\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\]
and
\[\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}\]
have the same optimal value for every choice of the vector $\mathbf{c}\in \mathbb{Z}_{+}^{E-e}$.

Let $A’$ be the matrix obtained by stacking a copy of $A$ on top of a copy of the identity matrix $I_{E-e}$. This means that the vector $\mathbf{x}\in\mathbb{R}^{E-e}$ is contained in the polytope $\mathcal{P}$ if and only if it satisfies the following system of inequalities:
\[A'\mathbf{x}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}.\]
If $\mathbf{x}$ is a vector in $\mathcal{P}$, then $A’_{\mathbf{x}}$ is the submatrix of $A’$ consisting of all rows $\mathbf{a}^{T}$ satisfying
\[
\mathbf{a}^{T}\mathbf{x}=
\begin{cases}
1 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ A\\
0 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ I_{E-e}
\end{cases}
\]
In other words, $A’_{\mathbf{x}}$ consists of all rows of $A’$ for which the corresponding inequality in the system
\[A'\mathbf{x}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}\]
is actually an equality for the vector $\mathbf{x}$. The vertices of $\mathcal{P}$ can be characterised by saying that they are the vectors $\mathbf{x}\in\mathcal{P}$ such that $A’_{\mathbf{x}}$ contains an $|E-e|\times |E-e|$ non-singular matrix.

Now assume that $\mathcal{P}$ has a vertex that does not have $0$-$1$ coordinates. We will show that $M$ is not $e$-flowing, and this will establish Lemma 1. To this end, assume that $\mathbf{x}_{0}$ is a vertex of $\mathcal{P}$ with at least one coordinate that is not $0$ or $1$. Let $A_{0}$ be an $|E-e|\times |E-e|$ non-singular submatrix of $A_{\mathbf{x}_{0}}$. Let $\mathbf{b}_{0}$ be the submatrix of the vector on the righthand side of
\[A'\mathbf{x}_{0}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}\]
consisting of rows that correspond to rows of $A_{0}$. This means that $\mathbf{x}_{0}$ is the unique solution to the equation $A_{0}\mathbf{x}=\mathbf{b}_{0}$. Define $\mathbf{c}^{T}$ to be the sum of the rows of $A_{0}$. Then $\mathbf{c}^{T}\mathbf{x}_{0}$ is equal to the weight of $\mathbf{b}_{\mathbf{x}}$. Let $\mathbf{x}’$ be any point in $\mathcal{P}$ other than $\mathbf{x}_{0}$. Since $\mathbf{x}’$ is not the unique solution to $A_{0}\mathbf{x}=\mathbf{b}_{\mathbf{x}}$, there is some row $\mathbf{a}^{T}$ in $A_{0}$ such that
\[
\mathbf{a}^{T}\mathbf{x}’ >
\begin{cases}
1 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ A\\
0 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ I_{E-e}
\end{cases}
\]
This means that $\mathbf{c}^{T}\mathbf{x}’$ is greater than the weight of $\mathbf{b}_{\mathbf{x}}$. It follows that $\mathbf{x}_{0}$ is the unique solution to the linear program
\[
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}
\]
so
\begin{multline*}
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}<\\
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\},
\end{multline*}
since $\mathbf{x}_{0}$ is not a $0$-$1$ vector.

Now if $\mathbf{y}$ and $\mathbf{x}$ are feasible points in, respectively, the programs
\[\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\]
and
\[\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\},\]
then $A\mathbf{x}\geq \mathbf{1}$, so $\mathbf{1}^{T} \leq \mathbf{x}^{T}A^{T}$. This means that
\[
\mathbf{1}^{T}\mathbf{y} \leq
(\mathbf{x}^{T}A^{T})\mathbf{y}=
\mathbf{x}^{T}(A^{T}\mathbf{y}) \leq
\mathbf{x}^{T}\mathbf{c} =
\mathbf{c}^{T}\mathbf{x}
\]
so
\begin{multline*}
\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\leq\\
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}.
\end{multline*}
(We can also deduce this using linear programming duality.) Combining this with the fact in the last paragraph, we see that
\begin{multline*}
\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}<\\
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}.
\end{multline*}
Hence the maximum value of a flow is strictly less than the minimum capacity of a cut, for this choice of the capacity function $\mathbf{c}$. This demonstrates that $M$ is not $e$-flowing, exactly as we wanted.

In fact, with a bit more work we can show that the converse also holds. That is, $M$ is $e$-flowing if and only if the vertices of $\mathcal{P}$ all have $0$-$1$ coordinates.

[Gue02] B. Guenin, Integral polyhedra related to even-cycle and even-cut matroids.
Math. Oper. Res. 27 (2002), no. 4, 693–710.

[Cor01] G. Cornuéjols, Combinatorial optimisation: Packing and covering. CBMS-NSF Regional Conference Series in Applied Mathematics, 74. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001.