اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMinimal counterexamples for contractible graphs and related notions
129
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The notion of a contractible transformation on a graph was introduced by Ivashchenko as a means to study molecular spaces arising from digital topology and computer image analysis, and more recently has been applied to topological data analysis. Contractible transformations involve a list of four elementary moves that can be performed on the vertices and edges of a graph, and it has been shown by Chen, Yau, and Yeh that these moves preserve the simple homotopy type of the underlying clique complex. A graph is said to be ${mathcal I}$-contractible if one can reduce it to a single isolated vertex via a sequence of contractible transformations. Inspired by the notions of collapsible and non-evasive simplicial complexes, in this paper we study certain subclasses of ${mathcal I}$-contractible graphs where one can collapse to a vertex using only a subset of these moves. Our main results involve constructions of minimal examples of graphs for which the resulting classes differ, as well as a miminal counterexample to an erroneous claim of Ivashchenko from the literature. We also relate these classes of graphs to the notion of $k$-dismantlable graphs and $k$-collapsible complexes, and discuss some open questions.
قيم البحث
اقرأ أيضاً
We construct explicit minimal models for the (hyper)operads governing modular, cyclic and ordinary operads, and wheeled properads, respectively. Algebras for these models are homoto
We study graphs with the property that every edge-colouring admits a monochromatic cycle (the length of which may depend freely on the colouring) and describe those graphs that are minimal with this property. We show that every member in this class r
educes recursively to one of the base graphs $K_5-e$ or $K_4vee K_4$ (two copies of $K_4$ identified at an edge), which implies that an arbitrary $n$-vertex graph with $e(G)geq 2n-1$ must contain one of those as a minor. We also describe three explicit constructions governing the reverse process. As an application we are able to establish Ramsey infiniteness for each of the three possible chromatic subclasses $chi=2, 3, 4$, the unboundedness of maximum degree within the class as well as Ramsey separability of the family of cycles of length $leq l$ from any of its proper subfamilies.
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.
A graph $G$ whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching $M$ that contains exactly one edge of each colour. We refute several conjectures on matchings in hypergraphs and full rainbow matc
hings in graphs, made by Aharoni and Berger and others.
Given graphs $H_1, dots, H_t$, a graph $G$ is $(H_1, dots, H_t)$-Ramsey-minimal if every $t$-coloring of the edges of $G$ contains a monochromatic $H_i$ in color $i$ for some $iin{1, dots, t}$, but any proper subgraph of $G $ does not possess this pr
operty. We define $mathcal{R}_{min}(H_1, dots, H_t)$ to be the family of $(H_1, dots, H_t)$-Ramsey-minimal graphs. A graph $G$ is dfn{$mathcal{R}_{min}(H_1, dots, H_t)$-saturated} if no element of $mathcal{R}_{min}(H_1, dots, H_t)$ is a subgraph of $G$, but for any edge $e$ in $overline{G}$, some element of $mathcal{R}_{min}(H_1, dots, H_t)$ is a subgraph of $G + e$. We define $sat(n, mathcal{R}_{min}(H_1, dots, H_t))$ to be the minimum number of edges over all $mathcal{R}_{min}(H_1, dots, H_t)$-saturated graphs on $n$ vertices. In 1987, Hanson and Toft conjectured that $sat(n, mathcal{R}_{min}(K_{k_1}, dots, K_{k_t}) )= (r - 2)(n - r + 2)+binom{r - 2}{2} $ for $n ge r$, where $r=r(K_{k_1}, dots, K_{k_t})$ is the classical Ramsey number for complete graphs. The first non-trivial case of Hanson and Tofts conjecture for sufficiently large $n$ was setteled in 2011, and is so far the only settled case. Motivated by Hanson and Tofts conjecture, we study the minimum number of edges over all $mathcal{R}_{min}(K_3, mathcal{T}_k)$-saturated graphs on $n$ vertices, where $mathcal{T}_k$ is the family of all trees on $k$ vertices. We show that for $n ge 18$, $sat(n, mathcal{R}_{min}(K_3, mathcal{T}_4)) =lfloor {5n}/{2}rfloor$. For $k ge 5$ and $n ge 2k + (lceil k/2 rceil +1) lceil k/2 rceil -2$, we obtain an asymptotic bound for $sat(n, mathcal{R}_{min}(K_3, mathcal{T}_k))$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
