Ryser's Conjecture
In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs. This conjecture first appeared in 1971 in the Ph.D. thesis of J. R. Henderson, whose advisor was H. J. Ryser, Herbert John Ryser. Preliminaries A Matching in hypergraphs, matching in a hypergraph is a set of hyperedges such that each vertex appears in at most one of them. The largest size of a matching in a hypergraph ''H'' is denoted by \nu(H). A Vertex cover in hypergraphs, transversal (or vertex cover) in a hypergraph is a set of vertices such that each hyperedge contains at least one of them. The smallest size of a transversal in a hypergraph ''H'' is denoted by \tau(H). For every ''H'', \nu(H)\leq \tau(H), since every cover must contain at least one point from each edge in any matching. If H is ''r''-uniform (each hyperedge has exactly ''r'' vertices), then \tau(H) \leq r\cdot \nu(H), since the union of the edges from any maximal mat ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]