The dual version of Ryser’s conjecture

I talked about our new results related to Ryser’s conjecture in a previous post (also see an even earlier post). The conjecture, and its variants, have some interesting equivalent formulations in terms of edge colourings of graphs. While I was vaguely aware of that, I never looked into it in detail. Thanks to the new paper of DeBiasio, Kamel, McCourt and Sheats, I have now decided to study it properly (and share what I understand). In this post I would like to explain and prove this so-called duality.

Consider the following two statements (and try to prove them without reading forward):

(1) Given n points in \mathbb{R}^2, let k be the maximum number of points that you can choose from these such that no two points share an x or a y coordinate. Then these n points can be covered by k axis parallel lines, i.e., horizontal or vertical lines.

(2) Let G be a graph of independence number \alpha whose edges are coloured red or blue. Then the vertices of G can be covered by \alpha monochromatic sub-trees (different trees can have different colours but all the edges of one tree must have the same colour).

While both of these statements do have the common feature of being covering problems, it is not immediately clear that they are in fact both implied by the classical theorem of Kőnig. Ryser’s conjecture is a generalisation of this, which in terms of (1) can be seen as a generalisation to \mathbb{R}^n and in terms of (2) can be seen as a generalisation to r colours. We will focus on (2) here, as the connection to (1) is sort of immediate and I don’t know if the geometric point of view has any clear advantage.

Just as a recap, here is what Ryser conjectured. Given an r-partite r-uniform hypergraph H, we have \tau(H) \leq (r - 1) \nu(H), where \tau is the vertex cover number of a hypergraph and \nu is the matching number.

For a graph G, let tc_r(G) denote the smallest number of monochromatic connected subgraphs whose vertices cover V(G), over all r-edge colourings of G. Here a monochromatic connected subgraph can also be a single vertex. You can in fact take these subgraphs to be the connected components in the graph G_i formed by taking the edges coloured by the i-th colour. If the grah G_i is disconnected, then you get single vertex monochromatic subgraphs. Gyárfás observed that Ryser’s conjecture is equivalent to tc_r(G) \leq (r - 1) \alpha(G), for all graphs G. We will soon see why this is so.

Firstly, to get some familiarity with tc_r(G), observe that the well known fact that for any graph G, either G is a connected graph or its complement G^c is a connected graph, can be stated as tc_2(K_n) \leq 1 for all n. This is because we can look the edges of G and G^c giving us the 2-edge colouring of K_n, where n = |V(G)|. Also note that tc_r(G) \leq n_i, where n_i is the number of connected components in the graph G_i, given an r-edge colouring of G. The notation tc stands for tree cover, which comes from the fact that any connected graph has a spanning tree, and thus instead of covering with monochromatic connected subgraphs we can equivalently cover with monochromatic trees.

Let’s prove that these two conjectures are equivalent. So, say Ryser’s conjecture is true, and let G be a graph with each of its edge given a colour from \{1, \dots, r\}. Denote the subgraph formed by edges whose colour is i by G_i. Construct a hypergraph H as follows. The vertices of H are the connected components of G_i, for i = 1, \dots, r. These vertices are clearly partitioned into r sets, corresponding to the colour i. For each vertex v of G, define a hyperedge of H as the set of all monochromatic connected components that contain v. Each hyperedge has size r since for each i the vertex v is contained in a unique component of G_i. Thus, we have an r-partite r-uniform hypergrah H. See the images below for some concrete example.

Now a matching in H corresponds to a set of vertices in G such that no two of these vertices are together in any monochromatic connected component. In particular, there is no edge between in any two of these vertices. Therefore, \nu(H) \leq \alpha(G). A vertex cover of H corresponds to a collection of monochromatic components that cover all the vertices of G (as they correspond to the hyperedges of H). Therefore, tc_r(G) \leq \tau(H). Since we assumed that Ryser’s conjecture is true, we also have \tau(H) \leq (r - 1) \nu(H). Combining all of these inequalities, we get tc_r(G) \leq (r - 1) \alpha(G).

Now assume that the conjecture of Gyárfás is true, and let H be an r-partite r-uniform hypergraph. Construct a graph G, where each hyperedge is a vertex of G and two vertices are adjacent if the corresonding hyperedges intersect non-trivially. We colour an edge uv of G by the colour i if the hyperedges corresponding to u and v meet each other in the i-th part of the r-partition. If they meet in more than one parts, then pick a colour arbitrarily. Again, for concreteness, we can see that in the first image above starting from the hypergraph on the right hand side we reach the graph on the left hand side. In the second case, however, we get the following:

It follows directly from the definition that independent sets in the graph are in bijective correspondence with matchings in the hypergraph, and thus \alpha(G) = \nu(H). A monochromatic connected component in G, which is in fact a clique, corresponds to the vertex of the hypergraph where all of the hyperedges meet. Therefore, a cover of the vertices of the graph using monochromatic connected components gives rise to a vertex cover of H of the same size, which implies that \tau(H) \leq tc_r(G). Since tc_r(G) \leq (r - 1) \alpha(G) = (r - 1)\nu(H), we get \tau(H) \leq (r - 1) \nu(H), thus proving the equivalence of these conjectures.

This duality can be applied to other variants of Ryser as well. For example, in my work with Shagnik, Patrick and Tibor, we studied the min vertex cover size for the case when the hypergraph is t-intersecting, i.e., any two hyperedges share at least t vertices. This can be seen as determining min tc_r(K_n) with the added condition that in the edge colouring any two vertices are contained in at least t different monochromatic components. Another variant that we studied was that of k-wise t-intersecting hypergraphs. This can be seen as determining the tree cover number of the k-uniform complete hypergraphs, where every set of k vertices are contained in at least t different monochromatic components. In this formulation Király had already solved the problem for k \geq 3, t =1, which we were unaware of, and our work resolves the general case of arbitrary t \geq 1. This complete knowledge of the extremal function for k \geq 3, and very limited knowledge for k = 2 is quite interesting.

One particular advantage of the edge colouring formulation is that we have a richer structure there that can be exploited to study interesting variants that have no natural formulation in terms of hypergraphs. For this, and more, check out the paper of DeBiasio, Kamel, McCourt and Sheats. On the other hand, the hypergraphs formulation somehow feels more natural, and in fact many proofs (for example the r=3 case of Ryser) are best stated in terms of hypergraphs. So in conclusion, it’s a good idea to be aware of both.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Uncategorized and tagged , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s