matching

Strong matchings and covers ★★★

Author(s): Aharoni

Let be a hypergraph. A strongly maximal matching is a matching so that for every matching . A strongly minimal cover is a (vertex) cover so that for every cover .

Conjecture   If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

Question   Does every matching of hypercube extend to a Hamiltonian cycle?

Keywords: Hamiltonian cycle; hypercube; matching

Ryser's conjecture ★★★

Author(s): Ryser

Conjecture   Let be an -uniform -partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .

Keywords: hypergraph; matching; packing