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 points in , let be the maximum number of points that you can choose from these such that no two points share an or a coordinate. Then these points can be covered by axis parallel lines, i.e., horizontal or vertical lines.
(2) Let be a graph of independence number whose edges are coloured red or blue. Then the vertices of can be covered by 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 and in terms of (2) can be seen as a generalisation to 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.
For a graph , let denote the smallest number of monochromatic connected subgraphs whose vertices cover , over all -edge colourings of . 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 formed by taking the edges coloured by the -th colour. If the grah is disconnected, then you get single vertex monochromatic subgraphs. Gyárfás observed that Ryser’s conjecture is equivalent to , for all graphs . We will soon see why this is so.
Firstly, to get some familiarity with , observe that the well known fact that for any graph , either is a connected graph or its complement is a connected graph, can be stated as for all . This is because we can look the edges of and giving us the -edge colouring of , where . Also note that , where is the number of connected components in the graph , given an -edge colouring of . The notation 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 be a graph with each of its edge given a colour from . Denote the subgraph formed by edges whose colour is by . Construct a hypergraph as follows. The vertices of are the connected components of , for . These vertices are clearly partitioned into sets, corresponding to the colour . For each vertex of , define a hyperedge of as the set of all monochromatic connected components that contain . Each hyperedge has size since for each the vertex is contained in a unique component of . Thus, we have an -partite -uniform hypergrah . See the images below for some concrete example.
Now a matching in corresponds to a set of vertices in 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, . A vertex cover of corresponds to a collection of monochromatic components that cover all the vertices of (as they correspond to the hyperedges of ). Therefore, . Since we assumed that Ryser’s conjecture is true, we also have . Combining all of these inequalities, we get .
Now assume that the conjecture of Gyárfás is true, and let be an -partite -uniform hypergraph. Construct a graph , where each hyperedge is a vertex of and two vertices are adjacent if the corresonding hyperedges intersect non-trivially. We colour an edge of by the colour if the hyperedges corresponding to and meet each other in the -th part of the -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 . A monochromatic connected component in , 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 of the same size, which implies that . Since , we get , 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 -intersecting, i.e., any two hyperedges share at least vertices. This can be seen as determining min with the added condition that in the edge colouring any two vertices are contained in at least different monochromatic components. Another variant that we studied was that of -wise -intersecting hypergraphs. This can be seen as determining the tree cover number of the -uniform complete hypergraphs, where every set of vertices are contained in at least different monochromatic components. In this formulation Király had already solved the problem for , which we were unaware of, and our work resolves the general case of arbitrary . This complete knowledge of the extremal function for , and very limited knowledge for 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 case of Ryser) are best stated in terms of hypergraphs. So in conclusion, it’s a good idea to be aware of both.