Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question
"have non-empty intersection with every subset of $W$" -- did you mean "every element of $W$"? – Bjørn Kjos-Hanssen Mar 9 '14 at 7:04
Yes of course I meant every element of $W$ or perhaps "every subset of $S$ in $W$". – Jeremy Kahn Mar 9 '14 at 19:17

2 Answers 2

up vote 3 down vote accepted

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.

share|cite|improve this answer
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. – Bjørn Kjos-Hanssen Mar 9 '14 at 8:00
Or you can let $v = (1/2,\,1/2,\, 1/2)$, the closest point to the origin of $W^\perp$. – Jeremy Kahn Mar 9 '14 at 19:24

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$.

share|cite|improve this answer
After 5 hours we both answer within the same minute! :) – Bjørn Kjos-Hanssen Mar 9 '14 at 7:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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