9
$\begingroup$

Definition 1: A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.

where,

vertex cover of $C$ is a set of vertices that have non-empty intersection with all of the edges. The minimum cardinality of a vertex cover of $C$ will be denoted by $\alpha_0(C)$. A matching (or independent set) of $C$ is a set of pairwise disjoint edges. The maximum cardinality of a matching in $C$ will be denoted by $\beta_1(C)$.

A clutter $C$ is said to satisfy the König property if $\alpha_0(C) =\beta_1(C)$.

For a vertex $x \in V (C)$, the deletion $C \setminus x$ is formed by removing $x$ from the vertex set and deleting any edge in $C$ that contains $x$. The contraction $C/x$ is obtained by $V(C/x) = V (C) \setminus x$ and $E \in E(C/x)$ if $x \notin E$ and either $E \in E(C)$ or $E \cup \{x\} \in E(C)$.

Any clutter formed by a sequence of deletions and contractions is called a minor of $C$.

Definition 2: $$\min \{ \langle w,v \rangle \mid v \geq 0; vA^T \geq 1\} =\max \{\langle y,1 \rangle\mid y \geq 0; Ay \leq w\}, $$ where $A$ is an incidence matrix of $C$.

The packing property can also be restated in terms of the dual linear programming system. An ideal has the packing property if and only if the dual linear programming system as above has integral optimal solutions for all $(0, 1,\infty)$-vectors $w$, that is, when entries of $w$ are all $0, 1$ or $\infty$.

Question : How to prove Definition 1 <=> Definition 2?

$\endgroup$

1 Answer 1

8
$\begingroup$

That Def 1 and Def 2 are equivalent is a well-known Conjecture, still open as far as I know. Curiously, you can translate the whole conjecture to the language of commutative algebra, see for example page 26 of this survey. It is relatively easy to prove 2 implies 1, it is the other direction that's problematic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .