0
$\begingroup$

Let $\ (V\ E)\ $ be a graph, i.e. $\ E\subseteq\binom V2.\ $ A $2$-lift pattern of a graph is a function $\ e:E\rightarrow\{-1\,\ 1\}.\ $ The induced 2-lift is defined as the graph $\ V\times\{-1\,\ 1\}\,\ E_e\ $ where

$$E_e\:=\ \{\{(a\ s)\,\ (b\ t)\}\ :\ \{a\ b\}\in V\ \ and\ \ t=e(\{a\ b\})\cdot s\}$$

  • Now by looking at the $2$-lift pattern can one say if the lifted graph is connected or not?
Improve this question
$\endgroup$
2
  • $\begingroup$ Is this "abstract" matrix or matrix tied to the graph? In the former case, probably "no"; in the latter, certainly "yes". $\endgroup$
    – Alex Degtyarev
    Commented Jan 18, 2015 at 10:10
  • $\begingroup$ Didn't get your question. I didn't define anything called the "abstract" matrix! I defined a "signing" matrix. $\endgroup$
    – user6818
    Commented Jan 18, 2015 at 10:25

1 Answer 1

Reset to default
2
$\begingroup$

Still, I don't understand the question. The matrix determines the graph, hence there is a way to tell whether it's connected. If the question is about how to do that, then here is the first thing that comes to my mind:

the double is connected iff (1) the original graph $G$ is connected, and (2) the homomorphism $H_1(G)\to\Bbb Z_2$ defined by the $2$-lift pattern is nontrivial.

Condition (2) can be restated as follows: there is a $1$-cycle spanned by the original vertices $i_1,i_2,\ldots,i_k,i_{k+1}=i_1$ such that $\prod_{j=1}^k e(\{i_j\ i_{j+1}\})=-1$.

Improve this answer
$\endgroup$
18
  • $\begingroup$ You have answered the question. Then what do you still not understand about the question? :) $\endgroup$
    – user6818
    Commented Jan 21, 2015 at 0:55
  • $\begingroup$ Can you give a reference to a proof of this condition that you stated? Is there a spectral way to check it? $\endgroup$
    – user6818
    Commented Jan 21, 2015 at 0:56
  • $\begingroup$ Any textbook in algebraic topology. What you call a $2$-lift is a double covering. Such coverings over $G$ are classified by their characteristic classes $\omega\in H^1(G;\Bbb Z/2)$ and, assuming $G$ connected, the covering is connected iff $\omega\ne0$. The rest is a computation of $\omega$ in terms of cellular complexes. I don't know what "spectral" means in these settings. $\endgroup$
    – Alex Degtyarev
    Commented Jan 21, 2015 at 7:09
  • $\begingroup$ I was asking if there is a reference you know which proves these for graphs. Like given a graph $G$, how would one calculate $H^1 (G, \mathbb{Z}/n)$? What other properties for general covering spaces go down to graph lifts? $\endgroup$
    – user6818
    Commented Jan 22, 2015 at 1:31
  • $\begingroup$ It is not clear to me as to why the condition you said about product of signs along a cycle being $-1$ is the same as guaranteeing that the lift is non-trivial and hence that the cover is connected. I am missing these two implications. [...my algebraic topology is very rusty...] Can you may be sketch the idea if it is short? $\endgroup$
    – user6818
    Commented Jan 22, 2015 at 2:18

Not the answer you're looking for? Browse other questions tagged .