packing


Inequality of the means ★★★

Author(s):

\begin{question} Is is possible to pack $n^n$ rectangular $n$-dimensional boxes each of which has side lengths $a_1,a_2,\ldots,a_n$ inside an $n$-dimensional cube with side length $a_1 + a_2 + \ldots a_n$? \end{question}

Keywords: arithmetic mean; geometric mean; Inequality; packing

Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

\begin{conjecture} Let $r \ge 2$ be an integer and let $H$ be a minor minimal \Def{clutter} with $\frac{1}{r}\tau_r(H) < \tau(H)$. Then either $H$ has a $J_k$ minor for some $k \ge 2$ or $H$ has Lehman's property. \end{conjecture}

Keywords: clutter; covering; MFMC property; packing

Woodall's Conjecture ★★★

Author(s): Woodall

\begin{conjecture} If $G$ is a directed graph with smallest directed cut of size $k$, then $G$ has $k$ disjoint dijoins. \end{conjecture}

Keywords: digraph; packing

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

Packing T-joins ★★

Author(s): DeVos

\begin{conjecture} There exists a fixed constant $c$ (probably $c=1$ suffices) so that every graft with minimum $T$-cut size at least $k$ contains a $T$-join packing of size at least $(2/3)k-c$. \end{conjecture}

Keywords: packing; T-join

Syndicate content