اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTopology of Hom complexes and test graphs for bounding chromatic number
156
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
It is shown that if T is a connected nontrivial graph and X is an arbitrary finite simplicial complex, then there is a graph G such that the complex Hom(T,G) is homotopy equivalent to X. The proof is constructive, and uses a nerve lemma. Along the wa
y several results regarding Hom complexes, exponentials, and subdivision are established that may be of independent interest.
Ramanujan complexes are high dimensional simplical complexes generalizing Ramanujan graphs. A result of Oh on quantitative property (T) for Lie groups over local fields is used to deduce a Mixing Lemma for such complexes. As an application we prove t
hat non-partite Ramanujan complexes have high girth and high chromatic number, generalizing a well known result about Ramanujan graphs.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
