Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHomomorphism complexes, reconfiguration, and homotopy for directed graphs
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The neighborhood complex of a graph was introduced by Lovasz to provide topological lower bounds on chromatic number, and more general homomorphism complexes of graphs were further studied by Babson and Kozlov. Such `Hom complexes are also related to reconfiguration problems and a notion of discrete homotopy for graphs. Here we initiate the detailed study of Hom complexes for directed graphs, which have applications in the study of graded posets and resolutions of monomial ideals. Our construction can be seen as a special case of the poset structure on the set of multihomomorphisms in more general categories, as introduced by Kozlov, Matsushita, and others. We relate the topological properties of Hom complexes to certain digraph operations including products, adjunctions, and foldings. We introduce a notion of a neighborhood complex for a directed graph and prove that its homotopy type is recovered as a certain Hom complex. We establish a number of results regarding the topology of these complexes, including the dependence on directed bipartite subgraphs, a directed version of the Mycielksi construction, as well as vanishing theorems for higher homology. Inspired by notions of reconfigurations of directed graph colorings we study the connectivity of Hom complexes into tournaments $T_n$. We obtain a complete answer for the case of transitive $T_n$, where we also describe a connection to mixed subdivisions of dilated simplices. Finally we use paths in the internal hom objects of directed graphs to define various notions of homotopy, and discuss connections to the topology of Hom complexes.
rate research
Read More
The notion of $times$-homotopy from cite{DocHom} is investigated in the context of the category of pointed graphs. The main result is a long exact sequence that relates the higher homotopy groups of the space $Hom_*(G,H)$ with the homotopy groups of $Hom_*(G,H^I)$. Here $Hom_*(G,H)$ is a space which parametrizes pointed graph maps from $G$ to $H$ (a pointed version of the usual $Hom$ complex), and $H^I$ is the graph of based paths in $H$. As a corollary it is shown that $pi_i big(Hom_*(G,H) big) cong [G,Omega^i H]_{times}$, where $Omega H$ is the graph of based closed paths in $H$ and $[G,K]_{times}$ is the set of $times$-homotopy classes of pointed graph maps from $G$ to $K$. This is similar in spirit to the results of cite{BBLL}, where the authors seek a space whose homotopy groups encode a similarly defined homotopy theory for graphs. The categorical connections to those constructions are discussed.
We investigate a notion of $times$-homotopy of graph maps that is based on the internal hom associated to the categorical product in the category of graphs. It is shown that graph $times$-homotopy is characterized by the topological properties of the $Hom$ complex, a functorial way to assign a poset (and hence topological space) to a pair of graphs; $Hom$ complexes were introduced by Lov{a}sz and further studied by Babson and Kozlov to give topological bounds on chromatic number. Along the way, we also establish some structural properties of $Hom$ complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. Graph $times$-homotopy naturally leads to a notion of homotopy equivalence which we show has several equivalent characterizations. We apply the notions of $times$-homotopy equivalence to the class of dismantlable graphs to get a list of conditions that again characterize these. We end with a discussion of graph homotopies arising from other internal homs, including the construction of `$A$-theory associated to the cartesian product in the category of reflexive graphs.
A flag complex can be defined as a simplicial complex whose simplices correspond to complete subgraphs of its 1-skeleton taken as a graph. In this article, by introducing the notion of s-dismantlability, we shall define the s-homotopy type of a graph and show in particular that two finite graphs have the same s-homotopy type if, and only if, the two flag complexes determined by these graphs have the same simplicial simple-homotopy type (Theorem 2.10, part 1). This result is closely related to similar results established by Barmak and Minian (Adv. in Math., 218 (2008), 87-104) in the framework of posets and we give the relation between the two approaches (theorems 3.5 and 3.7). We conclude with a question about the relation between the s-homotopy and the graph homotopy defined by Chen, Yau and Yeh (Discrete Math., 241(2001), 153-170).
We introduce new methods for understanding the topology of $Hom$ complexes (spaces of homomorphisms between two graphs), mostly in the context of group actions on graphs and posets. We view $Hom(T,-)$ and $Hom(-,G)$ as functors from graphs to posets, and introduce a functor $(-)^1$ from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations of the equivariant homotopy type of $Hom$ complexes in terms of spaces of equivariant poset maps and $Gamma$-twisted products of spaces. When $P = F(X)$ is the face poset of a simplicial complex $X$, this provides a useful way to control the topology of $Hom$ complexes. Our foremost application of these results is the construction of new families of `test graphs with arbitrarily large chromatic number - graphs $T$ with the property that the connectivity of $Hom(T,G)$ provides the best possible lower bound on the chromatic number of $G$. In particular we focus on two infinite families, which we view as higher dimensional analogues of odd cycles. The family of `spherical graphs have connections to the notion of homomorphism duality, whereas the family of `twisted toroidal graphs lead us to establish a weakened version of a conjecture (due to Lov{a}sz) relating topological lower bounds on chromatic number to maximum degree. Other structural results allow us to show that any finite simplicial complex $X$ with a free action by the symmetric group $S_n$ can be approximated up to $S_n$-homotopy equivalence as $Hom(K_n,G)$ for some graph $G$; this is a generalization of a result of Csorba. We conclude the paper with some discussion regarding the underlying categorical notions involved in our study.
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,sigma)$, equipped with lists $L(v) subseteq V(H), v in V(G)$, of allowed images, to a fixed target signed graph $(H,pi)$. The complexity of the similar homomorphism problem without lists (corresponding to all lists being $L(v)=V(H)$) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when $H$ is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and we illustrate this by classifying the complexity of irreflexive signed graphs in which the unicoloured edges form some simple structures, namely paths or cycles. The structure of the signed graphs in the polynomial cases is interesting, suggesting they may constitute a nice class of signed graphs analogous to the so-called bi-arc graphs (which characterized the polynomial cases of list homomorphisms to unsigned graphs).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
