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. Cont
ractible 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.
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.
We study homological properties of random quadratic monomial ideals in a polynomial ring $R = {mathbb K}[x_1, dots x_n]$, utilizing methods from the Erd{o}s-R{e}nyi model of random graphs. Here for a graph $G sim G(n, p)$ we consider the `coedge idea
l $I_G$ corresponding to the missing edges of $G$, and study Betti numbers of $R/I_G$ as $n$ tends to infinity. Our main results involve fixing the edge probability $p = p(n)$ so that asymptotically almost surely the Krull dimension of $R/I_G$ is fixed. Under these conditions we establish various properties regarding the Betti table of $R/I_G$, including sharp bounds on regularity and projective dimension, and distribution of nonzero normalized Betti numbers. These results extend work of Erman and Yang, who studied such ideals in the context of conjectured phenomena in the nonvanishing of asymptotic syzygies. Along the way we establish results regarding subcomplexes of random clique complexes as well as notions of higher-dimensional vertex $k$-connectivity that may be of independent interest.
We say that a pure $d$-dimensional simplicial complex $Delta$ on $n$ vertices is shelling completable if $Delta$ can be realized as the initial sequence of some shelling of $Delta_{n-1}^{(d)}$, the $d$-skeleton of the $(n-1)$-dimensional simplex. A w
ell-known conjecture of Simon posits that any shellable complex is shelling completable. In this note we prove that vertex decomposable complexes are shelling completable. In fact we show that if $Delta$ is a vertex decomposable complex then there exists an ordering of its ground set $V$ such that adding the revlex smallest missing $(d+1)$-subset of $V$ results in a complex that is again vertex decomposable. We explore applications to matroids, shifted complexes, as well as $k$-vertex decomposable complexes. We also show that if $Delta$ is a $d$-dimensional complex on at most $d+3$ vertices then the notions of shellable, vertex decomposable, shelling completable, and extendably shellable are all equivalent.
Motivated by the notion of chip-firing on the dual graph of a planar graph, we consider `integral flow chip-firing on an arbitrary graph $G$. The chip-firing rule is governed by ${mathcal L}^*(G)$, the dual Laplacian of $G$ determined by choosing a b
asis for the lattice of integral flows on $G$. We show that any graph admits such a basis so that ${mathcal L}^*(G)$ is an $M$-matrix, leading to a firing rule on these basis elements that is avalanche finite. This follows from a more general result on bases of integral lattices that may be of independent interest. Our results provide a notion of $z$-superstable flow configurations that are in bijection with the set of spanning trees of $G$. We show that for planar graphs, as well as for the graphs $K_5$ and $K_{3,3}$, one can find such a flow M-basis that consists of cycles of the underlying graph. We consider the question for arbitrary graphs and address some open questions.
A well-known conjecture of Richard Stanley posits that the $h$-vector of the independence complex of a matroid is a pure ${mathcal O}$-sequence. The conjecture has been established for various classes but is open for graphic matroids. A biconed graph
is a graph with two specified `coning vertices, such that every vertex of the graph is connected to at least one coning vertex. The class of biconed graphs includes coned graphs, Ferrers graphs, and complete multipartite graphs. We study the $h$-vectors of graphic matroids arising from biconed graphs, providing a combinatorial interpretation of their entries in terms of `edge-rooted forests of the underlying graph. This generalizes constructions of Kook and Lee who studied the Mobius coinvariant (the last nonzero entry of the $h$-vector) of graphic matroids of complete bipartite graphs. We show that allowing for partially edge-rooted forests gives rise to a pure multicomplex whose face count recovers the $h$-vector, establishing Stanleys conjecture for this class of matroids.
We prove that for all $d geq 1$ a shellable $d$-dimensional simplicial complex with at most $d+3$ vertices is extendably shellable. The proof involves considering the structure of `exposed edges in chordal graphs as well as a connection to linear quotients of quadratic monomial ideals.
A graph $G$ is said to be chordal if it has no induced cycles of length four or more. In a recent preprint Culbertson, Guralnik, and Stiller give a new characterization of chordal graphs in terms of sequences of what they call `edge-erasures. We show
that these moves are in fact equivalent to a linear quotient ordering on $I_{overline{G}}$, the edge ideal of the complement graph. Known results imply that $I_{overline G}$ has linear quotients if and only if $G$ is chordal, and hence this recovers an algebraic proof of their characterization. We investigate higher-dimensional analogues of this result, and show that in fact linear quotients for more general circuit ideals of $d$-clutters can be characterized in terms of removing exposed circuits in the complement clutter. Restricting to properly exposed circuits can be characterized by a homological condition. This leads to a notion of higher dimensional chordal clutters which borrows from commutative algebra and simple homotopy theory. The interpretation of linear quotients in terms of shellability of simplicial complexes also has applications to a conjecture of Simon regarding the extendable shellability of $k$-skeleta of simplices. Other connections to combinatorial commutative algebra, chordal complexes, and hierarchical clustering algorithms are explored.
Parking functions are a widely studied class of combinatorial objects, with connections to several branches of mathematics. On the algebraic side, parking functions can be identified with the standard monomials of $M_n$, a certain monomial ideal in t
he polynomial ring $S = {mathbb K}[x_1, dots, x_n]$ where a set of generators are indexed by the nonempty subsets of $[n] = {1,2,dots,n}$. Motivated by constructions from the theory of chip-firing on graphs we study generalizations of parking functions determined by $M^{(k)}_n$, a subideal of $M_n$ obtained by allowing only generators corresponding to subsets of $[n]$ of size at most $k$. For each $k$ the set of standard monomials of $M^{(k)}_n$, denoted $text{stan}_n^k$, contains the usual parking functions and has interesting combinatorial properties in its own right. For general $k$ we show that elements of $text{stan}_n^k$ can be recovered as certain vector-parking functions, which in turn leads to a formula for their count via results of Yan. The symmetric group $S_n$ naturally acts on the set $text{stan}_n^k$ and we also obtain a formula for the number of orbits under this action. For the case of $k = n-2$ we study combinatorial interpretations of $text{stan}_n^{n-2}$ and relate them to properties of uprooted trees in terms of root degree and surface
Given a graph $G$, the $G$-parking function ideal $M_G$ is an artinian monomial ideal in the polynomial ring $S$ with the property that a linear basis for $S/M_G$ is provided by the set of $G$-parking functions. It follows that the dimension of $S/M_
G$ is given by the number of spanning trees of $G$, which by the Matrix Tree Theorem is equal to the determinant of the reduced Laplacian of $G$. The ideals $M_G$ and related algebras were introduced by Postnikov and Shapiro where they studied their Hilbert functions and homological properties. The author and Sanyal showed that a minimal resolution of $M_G$ can be constructed from the graphical hyperplane arrangement associated to $G$, providing a combinatorial interpretation of the Betti numbers. Motivated by constructions in the theory of chip-firing on graphs, we study certain `skeleton ideals $M_G^{(k)} subset M_G$ generated by subsets of vertices of $G$ of size at most $k+1$. Here we focus our attention on the case $k=1$, the $1$-skeleton of the $G$-parking functions ideals. We consider standard monomials of $M_G^{(1)}$ and provide a combinatorial interpretation for the dimension of $S/M_G^{(1)}$ in terms of the signless Laplacian for the case $G = K_{n+1}$ is the complete graph. Our main study concerns homological properties of these ideals. We study resolutions of $M_G^{(1)}$ and show that for a certain class of graphs minimal resolution is supported on decompositions of Euclidean space coming from the theory of tropical hyperplane arrangements. This leads to combinatorial interpretations of the Betti numbers of these ideals.
