4
$\begingroup$

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\hat W$ of $W$ is the set of all subsets of $S$ that have non-empty intersection with every subset of $W$. The positive linear dual, for our purposes, is the set $W^\perp$ of all $v \in \mathbb R^S$ with non-negative entries such that $v \cdot w \ge 1$ for all $w \in W$. The convex production of a finite set $F \subset [0, \infty)^S$ is the set of vectors of the form $v + w$, where $v$ is in the convex hull of $F$, and $w \in [0, \infty)^S$. My first question is

Is $W^\perp$ always the convex production of $\hat W$?

It is clear that the latter is a subset of the former.

My second question is

Is the distance the origin of $W^\perp$ equal to the distance to the origin of the convex hull of $\hat W$?

Of course an affirmative answer to the first question would imply an affirmative answer to the second.

This question is motivated by a related question in the theory of combinatorial extremal length.

$\endgroup$
2
  • 1
    $\begingroup$ "have non-empty intersection with every subset of $W$" -- did you mean "every element of $W$"? $\endgroup$ Commented Mar 9, 2014 at 7:04
  • $\begingroup$ Yes of course I meant every element of $W$ or perhaps "every subset of $S$ in $W$". $\endgroup$ Commented Mar 9, 2014 at 19:17

2 Answers 2

3
$\begingroup$

No, let $S=\{1,2,3\}$, let $W$ consist of the "large" subsets of $S$, i.e., the ones of cardinality 2 or 3. Then $\hat W=W$. Let $v=(1/3,2/3,2/3)$. Then $v\in W^\bot$. But any vector in the convex production of $\hat W$ must lie above the half plane $x+y+z\ge 2$, which $v$ does not.

$\endgroup$
2
  • $\begingroup$ Oh and the distance to the origin of the plane $x+y+z=2$ is $2/\sqrt{3}$, whereas $v$ has length $1<2/\sqrt{3}$, so this also answers the second question. $\endgroup$ Commented Mar 9, 2014 at 8:00
  • $\begingroup$ Or you can let $v = (1/2,\,1/2,\, 1/2)$, the closest point to the origin of $W^\perp$. $\endgroup$ Commented Mar 9, 2014 at 19:24
2
$\begingroup$

Here is a counterexample to both: Let $W$ be the $2$-element subsets of a $4$-element set. The combinatorial dual is the collection of subsets of size $3$ or $4$. $W^\perp$ contains $(1/2, 1/2, 1/2, 1/2)$ which has coordinate sum $2$, while every element of $\hat W$ has coordinate sum at least $3$. The distance from the origin to the convex hull of $\hat W$ is $3/2$, while the distance to $(1/2,1/2,1/2,1/2)$ is $1$.

$\endgroup$
1
  • 1
    $\begingroup$ After 5 hours we both answer within the same minute! :) $\endgroup$ Commented Mar 9, 2014 at 7:58

You must log in to answer this question.

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