matching


Strong matchings and covers ★★★

Author(s): Aharoni

Let $H$ be a \Def{hypergraph}. A \emph{strongly maximal} matching is a matching $F \subseteq E(H)$ so that $|F' \setminus F| \le |F \setminus F'|$ for every matching $F'$. A \emph{strongly minimal} cover is a (vertex) cover $X \subseteq V(H)$ so that $|X' \setminus X| \ge |X \setminus X'|$ for every cover $X'$.

\begin{conjecture} If $H$ is a (possibly infinite) hypergraph in which all edges have size $\le k$ for some integer $k$, then $H$ has a strongly maximal matching and a strongly minimal cover. \end{conjecture}

Keywords: cover; infinite graph; matching

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

\begin{question} Does every \Def[matching]{matching} of \Def[hypercube]{hypercube} extend to a \Def[Hamiltonian cycle]{Hamiltonian path}? \end{question}

Keywords: Hamiltonian cycle; hypercube; matching

Ryser's conjecture ★★★

Author(s): Ryser

\begin{conjecture} Let $H$ be an $r$-\Def[uniform]{hypergraph} $r$-partite hypergraph. If $\nu$ is the maximum number of pairwise disjoint edges in $H$, and $\tau$ is the size of the smallest set of vertices which meets every edge, then $\tau \le (r-1) \nu$. \end{conjecture}

Keywords: hypergraph; matching; packing

Syndicate content