How to deconstruct a sum of intersecting upsets

Question

A set system $\mathcal{U}\subset P([n])$ is

• an upset if $B\supset A \in \mathcal{U}$ implies $B\in \mathcal{U}$,
• intersecting if $A,B\in\mathcal{U}$ implies $A\cap B \ne \emptyset$.

Note that a nonnegative linear combination of (indicator functions of) upsets is just an increasing function $f:P([n])\to[0,\infty)$, and it is a straightforward task to decompose any such $f$ back into its constituent upsets: just remove an appropriate multiple of $\mathcal{U}_1 = \lbrace A: f(A)>0 \rbrace$ and repeat.

However, given a nonnegative linear combination $f$ of intersecting upsets, how can one find appropriate intersecting upsets $\mathcal{U}_i$ and coefficients $\lambda_i$ such that $f = \sum \lambda_i \mathcal{U}_i$?

Answer 1

Here are a few comments which could be a start to a reasonable solution. I won't point out (after the first time) the difference between an upset and its indicator function.

A set system $\mathcal{A}\subset P([n])$ is an antichain if $B\supsetneq A \in \mathcal{A}$ implies $B\notin \mathcal{A}$

There is a natural bijection between upsets and antichains: The inclusion minimal elements of an upset $\mathcal{U}$ are an antichain $\mathcal{A}=\mathcal{A_U}$ and any antichain $\mathcal{A}$ determines an upset $\mathcal{U}=\mathcal{U_A}=\lbrace B \mid B\supseteq A \text{ for some } A \in \mathcal{A} \rbrace.$ An upset is intersecting exactly if the corresponding antichain is. A principal upset is one of the form $\mathcal{U}_{\lbrace A \rbrace}$

The set of non-negative non-decreasing functions on $P([n])$ is a convex cone (in $\mathbb{R}^{2^n}$.) We could normalize to have functions with $f(\emptyset)=0$ and $f([n])=1.$ Then we have a convex polytope $\mathbf(P)$ whose extreme points are the $0,1$ nondecreasing functions. These are just the (indicator functions of) upsets. The intersecting upsets span some smaller polytope $\mathbf{P'}$. For functions in $\mathbf{P'}$ we have $(*) f(A \cup B) \ge f(A)+f(B)$ when $A \cap B=\emptyset.$ This is because this property holds for intersecting upsets.

side question: Is the converse true -- Does the property $(*)$ characterize $\mathbf{P'}?$

We could think of a normalized non-decreasing function as giving a sort of confidence. Suppose an element $x \in [n]$ is going to be chosen somehow. I could ask you what likelihood $f(A)$ you would give as your confidence that $x$ is in the particular subset $A.$ At a minimum I would expect your $f$ to be non-decreasing with $f([n])=1.$ I might further expect property $(*)$ above.

I will now drop the assumption that $f$ is normalized and settle down to the question at hand.

It should be remarked that there can be many ways to decompose a non-decreasing function into a combination of upsets. Suppose that $A_1 \cap A_2 \neq \emptyset$ and $A_1 \cup A_2=A.$ Then $$U_{\lbrace A \rbrace} + U_{\lbrace A_1,A_2 \rbrace}-U_{\lbrace A_1 \rbrace}-U_{\lbrace A_2 \rbrace}=0 \tag{**}$$

There is a unique and easily found expression of an arbitrary function $f(\cdot)$ on $P[n]$ as a linear combination of the principal upsets, provided that negative coeffients are allowed. Then there might be standard algorithms for convex sets/cones to get $f(\cdot)$ as a positive combination of intersecting upsets (or discover that there is none.) However the request is probably for a satisfyingly efficient algorithm. Here is an operation which might (or might not) lead to such an algorithm (starting with the expansion just mentioned.)

Find a set $A$ with $\lambda_{\lbrace A \rbrace} \lt 0$. Use an appropriate multiple of a productive instance of $(**)$ to move $\lambda_A$ part way or all the way up to $0.$ The multiple should perhaps be $\min\left(\lambda_{\lbrace A_1 \rbrace},\lambda_{\lbrace A_2 \rbrace},-\lambda_{\lbrace A \rbrace} \right)$ or perhaps $-\lambda_{\lbrace A \rbrace}$ pushing the negative coefficient down. There may be useful variations involving intersecting antichains of more than two subsets.