Originator: Herbert Ryser, Chuan-Min Lee, Zsolt Tuza (presented by Tim LeSaulnier - REGS 2009)
Definitions: For a hypergraph H, the packing number (or matching number), most often written ν(H), is the maximum number of disjoint edges in H. A transversal is a set containing at least one vertex of each edge, and the transversal number, written τ(H), is the minimum size of a transversal. Trivially, τ(H)≥ν(H). A hypergraph is r-uniform if every edge has r vertices, and it is r-partite if the vertex set partitions into r sets such that no edge has more than one vertex in any set.
The cycle hypergraph of a graph G is the hypergraph with vertex set V(G) whose edges are the vertex sets of cycles in G. The cycle packing number of a graph G, denoted here by νc(G), is the packing number of the cycle hypergraph of G. A feedback vertex set of a graph G is a set of vertices whose deletion leaves an acyclic graph; that is, it is a transversal of the cycle hypergraph. Let τc(G) denote the minimum size of such a set, so τc(G)≥νc(G).
Background: The König-Egerváry Theorem [Ko] states that if H is a 2-uniform 2-partite hypergraph (a bipartite graph), then τ(H)≤ν(H). If H is r-uniform, then τ(H)≤rν(H), since the vertices in the edges of a maximal matching form a transversal (equality holds for the complete r-uniform hypergraph H when |V(H)|≡-1 mod r). Ryser conjectured a generalization of the K-E Theorem when H is also r-partite. Jones' and Tuza's Conjectures are conjectures with a similar flavor for hypergraphs made from cycles in graphs.
Conjecture 1: (Ryser's Conjecture) If H is an r-uniform r-partite hypergraph, then τ(H)≤(r-1)ν(H).
Comments: Ryser's Conjecture appeared in the thesis of his student J. Henderson in 1971. Aharoni [A] proved the conjecture for r=3, using a hypergraph generalization of Hall's Theorem by Aharoni and Haxell [AH] (the proof of [AH] is topological). It remains open for r≥4. Lovász [L] independently conjectured a stronger statement a bit later. The inequality in Ryser's Conjecture cannot be improved when r-1 is a prime power (Tuza [T]).
The matching number and transversal number problems are integer restrictions of linear programs, which may have fractional optima. The fractional matching number, written ν*(H), is the maximum sum of nonnegative weight on the edges such that the sum of the weights on the edges containing any vertex is at most 1. The fractional transversal number, written τ*(H), is the minimum sum of nonnegative weights on the vertices such that the total weight of the vertices in any edge is at least 1. Always τ(H)≥τ*(H)=ν*(H)≥ν(H). For r-regular r-partite hypergraphs, Füredi [F] proved that τ*(H)≤(r-1)ν(H), and Lovász [L] proved that τ(H)≤½rν*(H).
Conjecture 2: (Jones' Conjecture, Kloks-Lee-Liu [KLL]) If G is a planar graph, then τc(G)≤2νc(G).
Comments: It is easy to prove the desired bound when G is outerplanar, by induction. By the same inductive argument, the weaker result τc(G)≤5νc(G) holds for all planar graphs. If the graph is a 3-colorable triangulation and only facial cycles are included, then the conjecture becomes a special case of Aharoni's result on Ryser's Conjecture; however, planar graphs in general may have cycles of many lengths (including non-facial cycles), and there is no "partiteness" requirement.
Kloks, Lee, and Liu [KLL] note that Jones' Conjecture is sharp for wheels. They also showed that if G is a planar graph with τc(G)≤k, then tw(G) = O(k1/2), where tw(G) is the tree-width of G (and hence also tw(G) = O(ν(G)1/2), since τc(G)≤5νc(G) for planar graphs). Going beyond planar graphs, Erdős and Pósa [EP] constructed a family of graphs in which τc(G) = Θ(νc(G)logνc(G)).
Jones' Conjecture is named for Chuan-Min Lee, who also uses the name Jones.
Conjecture 3: (Tuza's Conjecture, 1981) If G is a graph, and H is the 3-uniform hypergraph whose vertices are the edges of G and whose edges are the sets of three edges in G that form 3-cycles, then τ(H)≤2ν(H).
Comments: More simply, the conjecture states that if G has at most k edge-disjoint triangles, then deleting some set of 2k edges breaks all triangles. Although these hypergraphs are 3-uniform, they are not 3-partite, so this requests the same bound as in Ryser's and Jones' Conjectures, but for a different family of hypergraphs. The conjecture has been proved when G is planar (Tuza [1985]), has no K3,3-subdivision (Krivelevich [Kr]), or tripartite (Haxell [1993]). Krivelevich [Kr] also proved that the inequality holds when either parameter is replaced with its fractional version. For a higher-dimensional generalization, see Ghosh-Haxell [GH].
References:
[A] R. Aharoni, Ryser's conjecture for tripartite 3-graphs. Combinatorica 21
(2001), no. 1, 1--4.
[AH] R. Aharoni and P. Haxell, Hall's theorem for hypergraphs. J. Graph Theory
35 (2000), no. 2, 83--88.
[EP] Erdős, P.; Pósa, L.; On independent circuits contained in a
graph. Canad. J. Math. 17 1965 347-352.
[F] Z. Füredi, Maximum degree and fractional matchings in uniform
hypergraphs, Combinatorica 1 (1981), 155--162.
[GH] Ghosh and P. Haxell, to appear.
[KLL] Kloks, Ton; Lee, C. M.; Liu, Jiping; New algorithms for k-face
cover, k-feedback vertex set, and k-disjoint cycles on plane and
planar graphs. Proceedings of the 28th International Workshop on
Graph-Theoretic Concepts in Computer Science (WG2002), LNCS 2573, pp.
282-295.
[Ko] D. König, Theorie der endlichen und unendlichen Graphen, Leipzig,
1936.
[Kr] Krivelevich, Michael; On a conjecture of Tuza about packing and covering of
triangles. Discrete Math. 142 (1995), no. 1-3, 281--286.
[L] L. Lovász, On minimax theorems of combinatorics, Ph.D thesis,
Matemathikai Lapok 26 (1975), 209--264 (in Hungarian).
[T]
Tuza, Zsolt;
Ryser's conjecture on transversals of r-partite hypergraphs.
Ars Combin. 16 (1983), B, 201--209.