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$ 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$ 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$ 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$ 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$ Mar 9, 2014 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.