Bertrand Guenin - The Cycling Conjecture

A family of sets over a finite groundset where no set is properly contained in another is a clutter. A cover of a clutter is a subset of the groundset that intersects every member of the clutter. The maximum number of pairwise disjoint sets in a clutter is the packing number and the cardinality of the smallest cover is the covering number. Clearly, the packing number is at most the covering number and a clutter packs if both numbers coincide. Not every clutter packs, consider for instance,

\[ \mathcal F=\{\{1,2\},\{1,3\},\{2,3\}\}, \]

then the packing number is \(1\) but the covering number is \(2\).

Examples of clutters that pack,

  1. The clutter of chains in posets (Dilworth),

  2. The clutter of st-paths (Menger),

  3. \(T\)-cuts in a graft with terminal \(T\) and bipartite graph (Seymour),

  4. odd cycles in odd-\(K_5\) free Eulerian graphs (Geelen, Guenin).

We will describe (4) in more details later. Examples (3) and (4) both involves a parity condition. For (3) all circuits have even length and for (4) all edge cuts have an even number of edges. The Cycling conjecture will provide sufficient conditions for a clutter, satisfying a particular parity condition, to pack.

The conjecture,

Consider a clutter \(\mathcal F\) with an element \(e\) of the groundset. The deletion minor \(\mathcal F\setminus e\) is defined as \(\{S\in\mathcal F: e\notin\mathcal F\}\), and the contraction minor \(\mathcal F/e\) is defined as the inclusion-wise minimal sets in \(\{S-\{e\}:S\in\mathcal F\}\). A minor of \(\mathcal F\) is a clutter obtained by a sequence of contractions and deletions.

A signed matroid is a pair \((M,\Sigma)\) where \(M\) is a binary matroid and \(\Sigma\subseteq EM\). A cycle of \(M\) is even (resp. odd) if \(|C\cap\Sigma|\) is even (resp. odd). Clearly, the set of inclusion-wise minimal odd cycles of \((M,\Sigma)\) is a clutter. Clutters that can be obtained by this construction are said to be binary.

A clutter \(\mathcal F\) is Eulerian if the parity of the cardinality of all inclusion-wise minimal covers is the same. At first glance this condition may appear non intuitive, so let us analyze what it says for a clutter \(\mathcal F\) of \(T\)-cuts in a graph \(G\) with terminals \(T\). The inclusion-wise minimal covers of \(\mathcal F\) are \(T\)-joins, and the parity of all \(T\)-joins is the same exactly when the symmetric difference of any two \(T\)-joins is a set with even cardinality. As the difference of two \(T\)-joins is an Eulerian subgraph, the condition translates to the requirement that \(G\) be bipartite.

We have the following conjecture that is essentially due to Seymour,

The Cycling Conjecture

An Eulerian binary clutter packs if it does not contain any of the following clutters as a minor,

  1. the Lines of the Fano,

  2. the odd circuits of \(K_5\),

  3. the complement of the cuts of \(K_5\), and

  4. the \(T\)-joins of the Petersen graph where \(T\) is the set of all vertices.

For (1) the groundset of the clutter are the elements of the Fano matroids, and the members the lines. For (2) and (3) the groundset are the edges of the complete graph on \(5\) vertices. Note for (2) the members are the triangles and the pentagons and for (3) the members are triangles together with an independent edge and complete graphs on four vertices. For (4) the groundset are the edges of the Petersen graph and the member subgraphs where every vertex has odd degree. This conjecture, is hard as we will see that it implies the Four Colour Theorem.

A special case of the conjecture,

A signed-graph is a pair \((G,\Sigma)\) where \(G\) is a graph and \(\Sigma\) is a subset of the edges. We say that \(B\subseteq E(G)\) is even (resp. odd) if \(|B\cap\Sigma|\) is even (resp. odd). We call a subset of the edges of \((G,\Sigma)\) where \(s,t\in V(G)\) an odd \(st\)-walk if it is either an odd \(st\)-path, or it is the union of an even \(st\)-path \(P\) and an odd circuit \(C\) where \(P\) and \(C\) share at most one vertex. We consider the empty set to be an (even) \(st\)-path for the case where \(s=t\). Thus when \(s=t\), odd \(st\)-walks are odd circuits. We proved that the Cycling conjecture holds for the clutter of odd \(st\)-walks, more precisely

Theorem 1

An Eulerian clutter of odd \(st\)-walks packs if it does not contain any of the following clutters as a minor,

  1. the Lines of the Fano,

  2. the odd circuits of \(K_5\).

The proof and applications can be found in [1], see in [2] an extended abstract. A fractional version of this result can be found in [3].

  • [1] A. Abdi and B. Guenin, The Two-Point Fano and Ideal Binary Clutters. In: Eisenbrand F., Koenemann J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2017. Lecture Notes in Computer Science, vol 10328. Springer, Cham. https://doi.org/10.1007/978-3-319-59250-3_1

  • [3] B. Guenin, Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids, Mathematics of Operations Research, Volume 27, Issue 4, November 2002, Pages 637-84, https:doi.org10.1287moor.27.4.693.299

Suppose \((G,\Sigma)\) is a signed-graph with vertices \(s,t\) and let \(\mathcal F\) be the clutter of odd \(st\)-walks of \((G,\Sigma)\). Then \(\mathcal F\) is Eulerian if either \(s=t\) and the degree of every vertex is even, or \(s\neq t\) and \(\deg(s)-|\Sigma|\) and the degree of every vertex in \(V(G)-\{s,t\}\) are even. The theorem states that in that case either: the maximum number of pairwise (edge) disjoint odd \(st\)-walks is equal to the minimum number of edges needed to intersect all odd \(st\)-walk, or \(\mathcal F\) must have as a minor the clutter of the lines of the Fano or the clutter of odd circuits of \(K_5\).

When \(s=t\), the condition that \({\mathcal F}\) is Eulerian says that all vertices of \(G\) have even degree. Moreover, in that case odd \(st\)-walks are odd circuits. Hence, Theorem 1 becomes,

Theorem 2

Let \(G\) be a graph that does not contain \(K_5\) as an odd minor and where every vertex has even degree. Then the minimum number of edges needed to intersect all odd circuits is equal to the maximum number of pairwise disjoint odd circuits.

  • [4] J. Geelen, B. Guenin, Packing odd circuits in Eulerian graphs. J. Combin. Theory Ser. B 86, 280–295, (2002)

A blocking vertex (resp. blocking pair) is a vertex (resp. pair of vertices) that intersects every odd circuit. Next we indicate a number of classes of signed-graphs for which the clutter of odd \(st\)-walks does not have as a minor the lines of the Fano or the clutter of odd circuits of \(K_5\).

  • (A) There exists a blocking vertex,

  • (B) \(s,t\) is a blocking pair,

  • (C) Every odd \(st\)-walk is connected,

  • (D) \(G\) is a plane graph with at most two odd faces,

  • (E) \(G\) is a plane graph with a blocking pair \(u,v\) where \(s,u,t,v\) appear on a facial cycle in this order,

  • (F) \(G\) has an embedding on the projective plane where every face is even and \(s, t\) are connected by an odd edge.

Thus for each of the classes of signed-graphs (A)-(F), as long as the Eulerian condition holds, the minimum number of edges needed to intersect all odd \(st\)-walk is equal to the maximum number of disjoint odd \(st\)-walks.

Applying Theorem 1 to class (A) we can obtain,

Corollary

Let \((H,T)\) be a graft with \(|T|\leq 4\). Suppose that every vertex of \(H\) not in \(T\) has even degree and that all the vertices in \(T\) have degrees of the same parity. Then the maximum number of pairwise disjoint \(T\)-joins is equal to the minimum size of a \(T\)-cut.

In fact this result holds as long as \(|T|\leq 8\).

Applying Theorem 1 to class (B) we can derive the two-commodity flow of Hu, Rothschild and Whinston, namely,

Corollary

Let \(H\) be a graph with vertices \(s_1,s_2,t_1,t_2\) where \(s_1\neq t_1\), \(s_2\neq t_2\), all of \(s_1,t_1,s_2,t_2\) have the same parity, and all the other vertices have even degree. Then the maximum number of pairwise disjoint paths that are between \(s_i\) and \(t_i\) for some \(i=1,2\), is equal to the minimum size of an edge subset whose deletion removes all \(s_1t_1\)- and \(s_2t_2\)-paths.

Consider \(G\) obtained as follows:

(\(\star\)) start from a plane graph with exactly two faces of odd length and distinct vertices \(s\) and \(t\), and identify \(s\) and \(t\).

Applying Theorem 1 to class (C) we can obtain,

Corollary

Let \(H\) be a graph as in (\(\star\)) and suppose that the length of the shortest odd circuit is \(k\). Then there exists cuts \(B_1,\ldots,B_k\) such that every edge \(e\) is in at least \(k-1\) of \(B_1,\ldots,B_k.\)

Suppose that \(H\) is as in (\(\star\)) and is loopless. Then by Corollary 6, there exists cuts \(\delta(U_1), \delta(U_2)\) such that every edge is in \(\delta(U_1)\cup\delta(U_2)\). It follows that for all \(i,j\in[4]\) where \(i\neq j\), \(U_i\cap U_j\) is a stable set. Hence, \(H\) is \(4\)-colourable.

The following conjecture would generalize the previous result as well as the 4-colour theorem,

Conjecture

Let \(H\) be a graph that does not contain \(K_5\) as an odd minor and suppose that the length of the shortest odd circuit is \(k\). Then there exists cuts \(B_1,\ldots,B_k\) such that every edge \(e\) is in at least \(k-1\) of \(B_1,\ldots,B_k\).

It can be shown that this conjecture is another special case of the Cycling Conjecture. It is open for planar graphs.

C&O