Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Reliability Roots of Simplicial Complexes and Matroids
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ fail independently with probability $q in[0,1]$. The emph{all-terminal reliability} of $G$ is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in $q$, and it was conjectured cite{BC1} that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when, for small simplicial complexes and matroids, the roots fall inside the closed unit disk.
rate research
Read More
Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ are operational independently with probability $p in[0,1]$. For fixed vertices $s$ and $t$, the emph{two-terminal reliability} of $G$ is the probability that the operational subgraph contains an $(s,t)$-path, while the emph{all-terminal reliability} of $G$ is the probability that the operational subgraph contains a spanning tree. Both reliabilities are polynomials in $p$, and have very similar behaviour in many respects. However, unlike all-terminal reliability, little is known about the roots of two-reliability polynomials. In a variety of ways, we shall show that the nature and location of the roots of two-terminal reliability polynomials have significantly different properties than those held by roots of the all-terminal reliability.
Motivated by Grobner basis theory for finite point configurations, we define and study the class of standard complexes associated to a matroid. Standard complexes are certain subcomplexes of the independence complex that are invariant under matroid duality. For the lexicographic term order, the standard complexes satisfy a deletion-contraction-type recurrence. We explicitly determine the lexicographic standard complexes for lattice path matroids using classical bijective combinatorics.
The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of $d$-cycles, $d$-hypertrees and $d$-hypercuts are, respectively, $(d+1)$, $d$, and $(n-d-1)$-vertex-connected. It is also shown that the facet graph of a $d$-cycle cannot be split into more than $s$ connected components by removing at most $s$ vertices. In addition, the paper discusses various related issues, as well as an extension to cell-complexes.
Let $X$ be a simplicial complex on vertex set $V$. We say that $X$ is $d$-representable if it is isomorphic to the nerve of a family of convex sets in $mathbb{R}^d$. We define the $d$-boxicity of $X$ as the minimal $k$ such that $X$ can be written as the intersection of $k$ $d$-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of $X$ is a set $tausubset V$ such that $tau otin X$ but $sigmain X$ for any $sigmasubsetneq tau$. We prove that the $d$-boxicity of a simplicial complex on $n$ vertices without missing faces of dimension larger than $d$ is at most $leftlfloorfrac{1}{d+1}binom{n}{d}rightrfloor$. The bound is sharp: the $d$-boxicity of a simplicial complex whose set of missing faces form a Steiner $(d,d+1,n)$-system is exactly $frac{1}{d+1}binom{n}{d}$.
We provide a simple characterization of simplicial complexes on few vertices that embed into the $d$-sphere. Namely, a simplicial complex on $d+3$ vertices embeds into the $d$-sphere if and only if its non-faces do not form an intersecting family. As immediate consequences, we recover the classical van Kampen--Flores theorem and provide a topological extension of the ErdH os--Ko--Rado theorem. By analogy with Farys theorem for planar graphs, we show in addition that such complexes satisfy the rigidity property that continuous and linear embeddability are equivalent.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
