The strong acyclicity characterization of initial segment complexes

At least 14 years old · documented by

Let [n]={1,…,n}[n]=\{1,\ldots,n\} and let Δ⊆2[n]\Delta\subseteq 2^{[n]} be a simplicial complex. Define the Winder desirability relation ≤W\leq_W on 2[n]2^{[n]} by A≤WBA\leq_W B if and only if, for every Z⊆[n]∖((A∖B)∪(B∖A))Z\subseteq[n]\setminus((A\setminus B)\cup(B\setminus A)),

(A∖B)∪Z∉Δ⇒(B∖A)∪Z∉Δ.(A\setminus B)\cup Z\notin\Delta\Rightarrow(B\setminus A)\cup Z\notin\Delta.

Define the Winder existential ordering by A≺WBA\prec_W B if and only if it is not the case that B≤WAB\leq_W A. The complex Δ\Delta is strongly acyclic when there is no cycle A1≺WA2≺W⋯≺WAk≺WA1A_1\prec_W A_2\prec_W\cdots\prec_W A_k\prec_W A_1 for any kk. An initial segment complex is one of the form Δ(⪯,T)\Delta(\preceq,T) for a qualitative probability order ⪯\preceq on 2[n]2^{[n]} and some T∈2[n]T\in2^{[n]}. Strong acyclicity conjecture. A simplicial complex Δ\Delta is an initial segment complex if and only if it is strongly acyclic. Theorem 3.1 establishes the necessary direction: every initial segment complex is strongly acyclic. The converse is supported by subsequent lemmas showing that the Winder existential ordering has the cancellation property needed for extension to a qualitative probability order, but it is not established here.

References

Primary source

Paul H. Edelman, Tatyana Gvozdeva and Arkadii Slinko, “Simplicial Complexes Obtained from Qualitative Probability Orders”, arXiv:1108.3700 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.