![](/files/happy5.png)
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.
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ \le k $](/files/tex/26d614fff037e5976f481eab5b4e36c487e120ac.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
Keywords: cover; infinite graph; matching
Matchings extend to Hamiltonian cycles in hypercubes ★★
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
.
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ r $](/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png)
![$ r $](/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png)
![$ \nu $](/files/tex/84ef96eb1030eaa1447d7a3c9ce8be567b7eccc8.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ \tau $](/files/tex/706065ef4c2d4b462dff91b9ad9fc69d846c15dc.png)
![$ \tau \le (r-1) \nu $](/files/tex/03ec477958b1e8cdfcb12ec5ef3d32014472a61d.png)
Keywords: hypergraph; matching; packing
![Syndicate content Syndicate content](/misc/feed.png)