Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLeray numbers of complexes of graphs with bounded matching number
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a graph $G$ on the vertex set $V$, the {em non-matching complex} of $G$, $NM_k(G)$, is the family of subgraphs $G subset G$ whose matching number $ u(G)$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of $NM_k(K_n)$ and $NM_k(K_{r,s})$ to arbitrary graphs $G$, we show that (i) $NM_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then $NM_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex $NM_k(G)$, which vanishes in all dimensions $dgeq 3k-4$, and all dimensions $d geq 2k-3$ when $G$ is bipartite. As a corollary, we have the following rainbow matching theorem which generalizes the result by Aharoni et. al. and Driskos theorem: Let $E_1, dots, E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $ u(E_icup E_j)geq k$ for every $i e j$. Then $E=bigcup E_i$ has a rainbow matching of size $k$. Furthermore, the number of edge sets $E_i$ can be reduced to $2k-1$ when $E$ is the edge set of a bipartite graph.
rate research
Read More
Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexes $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Delta$. Then, every collection of $leftlfloorleft(frac{Delta}{2}+1right)(n-1)rightrfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.
Let $K$ be a simplicial complex on vertex set $V$. $K$ is called $d$-Leray if the homology groups of any induced subcomplex of $K$ are trivial in dimensions $d$ and higher. $K$ is called $d$-collapsible if it can be reduced to the void complex by sequentially removing a simplex of size at most $d$ that is contained in a unique maximal face. We define the $t$-tolerance complex of $K$, $mathcal{T}_t(K)$, as the simplicial complex on vertex set $V$ whose simplices are formed as the union of a simplex in $K$ and a set of size at most $t$. We prove that for any $d$ and $t$ there exists a positive integer $h(t,d)$ such that, for every $d$-collapsible complex $K$, the $t$-tolerance complex $mathcal{T}_t(K)$ is $h(t,d)$-Leray. The definition of the complex $mathcal{T}_t(K)$ is motivated by results of Montejano and Oliveros on tolerant
We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. We show that $$ left(c cdot frac{kcdot 2^k cdot n}{log k} right)^n cdot 2^{-frac{k(k+3)}{2}} cdot k^{-2k-2} leq T_{n,k} leq left(k cdot 2^k cdot nright)^n cdot 2^{-frac{k(k+1)}{2}} cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.
The matching complex of a graph $G$ is a simplicial complex whose simplices are matchings in $G$. In the last few years the matching complexes of grid graphs have gained much attention among the topological combinatorists. In 2017, Braun and Hough obtained homological results related to the matching complexes of $2 times n$ grid graphs. Further in 2019, Matsushita showed that the matching complexes of $2 times n$ grid graphs are homotopy equivalent to a wedge of spheres. In this article we prove that the matching complexes of $3times n$ grid graphs are homotopy equivalent to a wedge of spheres. We also give the comprehensive list of the dimensions of spheres appearing in the wedge.
Let $mathscr{G}_{n,beta}$ be the set of graphs of order $n$ with given matching number $beta$. Let $D(G)$ be the diagonal matrix of the degrees of the graph $G$ and $A(G)$ be the adjacency matrix of the graph $G$. The largest eigenvalue of the nonnegative matrix $A_{alpha}(G)=alpha D(G)+A(G)$ is called the $alpha$-spectral radius of $G$. The graphs with maximal $alpha$-spectral radius in $mathscr{G}_{n,beta}$ are completely characterized in this paper. In this way we provide a general framework to attack the problem of extremal spectral radius in $mathscr{G}_{n,beta}$. More precisely, we generalize the known results on the maximal adjacency spectral radius in $mathscr{G}_{n,beta}$ and the signless Laplacian spectral radius.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
