6
$\begingroup$

$\DeclareMathOperator\width{width}$Let $P$ be a finite poset with $n$ elements (we can assume that $P$ is connected and has width at most $n-2$). The comparability graph $G_P=(V,E)$ associated to $P$ is by definition the finite graph with vertices $V=P$ and two elements $v, w \in V$ are adjacent if $v<w$ or $w<v$. A subset $S$ of $V$ is called a dominating set in $G$ if every vertex $v$ in $G$ belongs to $S$ or is adjacent to an element of $S$.

The dominance complex $D(G_P)$ is the simplicial complex consisting of the subsets of $V$ whose complements are dominating. We look at homology of such a simplicial complex over fields here (see Perkinson - Homology of Simplicial Complexes for a definition).

Question (Formulation 1): Is it true that the first degree in which the reduced homology is non-zero of $D(G_P)$ is equal to $n-1-\width(P)$?

(Here $\width(P)$ denotes the maximal cardinality of an antichain in the poset $P$.)

By theorem 1 in Matsushita - Dominance complex and vertex cover number, we should have that the first non-zero degree of the reduced homology is less than or equal to $n-1-\width(P)$. And the question asks whether we have equality in theorem 1 of the previous article in the case of graphs given as comparability graphs of finite posets.

Here is a more direct alternative formulation of the problem:

Let $P$ be a finite poset with $n$ elements (we can assume that $P$ is connected and the width of $P$ is at most $n-2$). For $p \in P$ set $J(p):=\{q \in P \mid p \nleq q \}$ and $I(p):= \{ q \in P \mid q \leq p \}$. For a subset $S \subseteq P$ set $J(S) := \bigcap\limits_{p \in S}{J(p)}$ and $I(S):= \bigcup\limits_{p \in S}{I(p)}$.

Then the simplicial complex $\Gamma(P)$ associated to $P$ is defined by the condition $S \in \Gamma(P)$ if and only if $J(S^c) \subseteq I(S^c)$.

Question (Formulation 2): Is it true that the first non-zero positive degree of the homology of $\Gamma(P)$ appears at $n-1-\width(P)$?

The question is tested with a computer and true for all posets with at most 10 elements (thus for nearly 3 million examples).

(Background: The original formulation of the question is Formulation 2 and the connection to the article Matsushita - Dominance complex and vertex cover number was noted by Hugh Thomas.)

$\endgroup$
12
  • 4
    $\begingroup$ Comparability graphs are a subclass of perfect graphs. Have you considered if the equality holds for all perfect graphs? $\endgroup$ Dec 20, 2021 at 19:42
  • $\begingroup$ @SamHopkins Thanks for the comment. The problem comes from homological algebra of incidence algebras of posets, so I have not studied the problem when there might be equality for a more general class of graphs yet. I might do some tests later related to perfect graphs. $\endgroup$
    – Mare
    Dec 20, 2021 at 19:44
  • 1
    $\begingroup$ @SamHopkins I think I found a counterexample for perfect graphs using Sage, see the answer below (I posted it as a community wiki answer as it is too long for a comment and also does not fit well into the question). $\endgroup$
    – Mare
    Dec 21, 2021 at 11:40
  • 3
    $\begingroup$ This is the combinatorial Alexander dual of the simplicial complex with simplices the non-dominating sets in the sense of arxiv.org/abs/0710.1172. Proving there is no homology beneath the given dimension is equivalent to proving there is no cohomology of the Alexander dual above dimension $\mathrm{width}(P)-2$. This might be helpful: one can hope to prove the conjecture by exhibiting a homotopy equivalence to a complex of dimension $w-2$. Also, over a field it is enough to show $H_i=0$ for $i\ge w-1$. Perhaps this gives a more intuitive picture. $\endgroup$ Dec 23, 2021 at 23:04
  • 1
    $\begingroup$ @Mare Perhaps the simplest tool for attempting computations like this mechanically is discrete Morse theory. I don't know if there is a Sage implementation. If there is, you should know that it can produce false negatives, in the sense that you may not find a homotopy equivalence even though one exists. However, it sometimes succeeds (on all examples) in this kind of combinatorial setting, perhaps after a barycentric subdivision or two of the complex, and sometimes it ends up being a tool for proving such statements. (Another less "computation-friendly" tool is Quillen theorem A for posets...) $\endgroup$ Dec 24, 2021 at 10:43

2 Answers 2

4
$\begingroup$

I made a Sage program to check whether the question has a positive answer for a given graph.

I found no counterexample yet for comparability graphs of posets. Here is the program to test it for a randomly generated poset:

P = posets.RandomPoset(14, 0.3)
display(P)
G = P.comparability_graph();
display(G)
def test_homologygraph(G):
    U = Subsets(G)
    GGU=Set(G)
    T=[t for t in U if G.is_dominating(GGU.difference(t))==true]
    TT=[list(r) for r in T]
    S=SimplicialComplex(TT)
    W=S.homology(base_ring=GF(2))
    tt=len(W)
    F=[dimension(W[t]) for t in [0..tt-1]]
    FF=[r for r in [0..tt-1] if F[r]>0]
    uu=min(FF)
    return(uu+1)

def conjecturetestforperfectgraph(G):
    oo=test_homologygraph(G)
    oo2=G.vertex_cover(value_only=True)
    return(oo==oo2)

display(conjecturetestforperfectgraph(G))

But it gave a counterexample for perfect graphs (one with 6 elements). Note that this is not part of the question in this thread but was a suggested in the comments as a generalisation of the question.

def test_homologygraph(G):
    U = Subsets(G)
    GGU=Set(G)
    T=[t for t in U if G.is_dominating(GGU.difference(t))==true]
    TT=[list(r) for r in T]
    S=SimplicialComplex(TT)
    W=S.homology(base_ring=GF(2))
    tt=len(W)
    F=[dimension(W[t]) for t in [0..tt-1]]
    FF=[r for r in [0..tt-1] if F[r]>0]
    uu=min(FF)
    return(uu+1)

def conjecturetestforperfectgraph(G):
    oo=test_homologygraph(G)
    oo2=G.vertex_cover(value_only=True)
    return(oo==oo2)
n=6
U=graphs(n)
UU=[g for g in U if g.is_perfect()]
n=len(UU)
UU2=[UU[t] for t in [1..n-1]]
UU3=[g for g in UU2 if conjecturetestforperfectgraph(g)==false]
G=UU3[0]
display(G)
display(conjecturetestforperfectgraph(G))

edit: Here a (new) program to test the conjecture for posets with $n$ points:

n=7
def test_homologyposet(P):
    G = P.comparability_graph();
    U = Subsets(G)
    GGU=Set(G)
    T=[t for t in U if G.is_dominating(GGU.difference(t))==true]
    TT=[list(r) for r in T]
    S=SimplicialComplex(TT)
    W=S.homology(base_ring=GF(2))
    tt=len(W)
    F=[dimension(W[t]) for t in [0..tt-1]]
    FF=[r for r in [0..tt-1] if F[r]>0]
    uu=min(FF)
    return(uu+1)

def conjecturetestforposet(P):
    G= P.comparability_graph();
    oo=test_homologyposet(P)
    oo2=G.vertex_cover(value_only=True)
    return(oo==oo2)

PP=Posets(n)
PP1=[p for p in PP if len(p)>p.width()+1]
PP2=[p for p in PP1 if conjecturetestforposet(p)==true]
display(PP1==PP2) 

Here the example for the join of two diamonds with 5 elements:

P1=posets.DiamondPoset(5)
P2=posets.DiamondPoset(5)
U=P1.ordinal_sum(P2)
display(U)
def test_homologyposet(P):
    G = P.comparability_graph();
    U = Subsets(G)
    GGU=Set(G)
    T=[t for t in U if G.is_dominating(GGU.difference(t))==true]
    TT=[list(r) for r in T]
    S=SimplicialComplex(TT)
    W=S.homology(base_ring=GF(2))
    tt=len(W)
    F=[dimension(W[t]) for t in [0..tt-1]]
    FF=[r for r in [0..tt-1] if F[r]>0]
    uu=min(FF)
    return(uu+1)

def conjecturetestforposet(P):
    G= P.comparability_graph();
    oo=test_homologyposet(P)
    oo2=G.vertex_cover(value_only=True)
    return(oo==oo2)

display(conjecturetestforposet(U))

Here how to calculate the homology over a field K of a given poset P (here a random poset):

P = posets.RandomPoset(14, 0.3)
display(P)
G = P.comparability_graph();
display(G)

def posethomology(G,K):
    U = Subsets(G)
    GGU=Set(G)
    T=[t for t in U if G.is_dominating(GGU.difference(t))==true]
    TT=[list(r) for r in T]
    S=SimplicialComplex(TT)
    W=S.homology(base_ring=K)
    return(W)

display(posethomology(G,ZZ))

display(posethomology(G,QQ))

display(posethomology(G,GF(2)))

Some random examples revealed that it can happen that there is a unique non-zero degree in which the homology has dimension/rank more than one.

$\endgroup$
0
$\begingroup$

This is too long for a comment so I post it as a community wiki answer.

I recently saw a result in the book "Ordered sets" by Schröder and I wonder whether it can be applied when choosing the right point v: Let $K=(V,S)$ be a (finite always) simplicial complex. Then the link complex $(N(v) \setminus \{v \},Lk(v))$ of a point $v$ is the simplicial complex with $N(v):= \{ w \in V | \{v,w \} \in S \}$ and $Lk(v)= \{ b \in S | \{v\} \cup b \in S , \{v\} \cap b = \emptyset \}$.

Then theorem A.18 in the book states:

Theorem: Let $K=(V,S)$ be a simplicial complex, $q \geq 1$ and let $v \in V$ be such that $H_q((N(v) \setminus \{v \},Lk(v)))= \{0 \}$. Then the followng hold:

a) If $q=1$ and $H_0((N(v) \setminus \{v \},Lk(v)))= \mathbb{Z}$, then $H_1(K)=H_1(K [V \setminus \{v \}])$.

b) If $q \geq 2$ and $H_{q-1}((N(v) \setminus \{v \},Lk(v)))= \{0\}$, then $H_q(K)= H_q(K[V \setminus \{v \}])$.

Corollary A.19 then states :

Corollary: Let $K(V,S)$ be a simplicial complex and $v \in V$ such that the link complex $(N(v) \setminus \{v \},Lk(v))$ is acyclic. Then, for all $q \in \mathbb{N} \cup \{0\}$, we have $H_q(K)=H_q(K[V \setminus \{v\}])$.

Maybe someone has an idea for a good choice of $v$ to use induction or another argument that might at least work for certain posets to prove the statement for the comparability graphs (or the alexander dual equivalent statement as in the comment by Geva Yashfe). I will do some computer tests whether such a thing can work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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