BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Steven Klee

Steven Klee appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRData Structures and Algorithmsmath.ACmath.GRmath.GTmath.HOmath.OC

Catalog footprint

What is connected

18works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2022arXiv

Sharp estimates for spanning trees

We prove the following sharp estimate for the number of spanning trees of a graph in terms of its vertex-degrees: a simple graph $G$ on $n$ vertices has at most $(1/n^{2}) \prod_{v \in V(G)} (d(v)+1)$ spanning trees. This result is tight (for complete graphs), and improves earlier estimates of Alon from 1990 and Kostochka from 1995 by a factor of about $1/n$ (for dense graphs). We additionally show that an analogous bound holds for the weighted spanning tree enumerator of a (nonnegatively) weighted graph as well.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Diameters of Cocircuit Graphs of Oriented Matroids: An Update

Oriented matroids (often called order types) are combinatorial structures that generalize point configurations, vector configurations, hyperplane arrangements, polyhedra, linear programs, and directed graphs. Oriented matroids have played a key role in combinatorics, computational geometry, and optimization. This paper surveys prior work and presents an update on the search for bounds on the diameter of the cocircuit graph of an oriented matroid. We review the diameter problem and show the diameter bounds of general oriented matroids reduce to those of uniform oriented matroids. We give the latest exact bounds for oriented matroids of low rank and low corank, and for all oriented matroids with up to nine elements (this part required a large computer-based proof). The motivation for our investigations is the complexity of the simplex method and the criss-cross method. For arbitrary oriented matroids, we present an improvement to a quadratic bound of Finschi. Our discussion highlights two very important conjectures related to the polynomial Hirsch conjecture for polytope diameters.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Eigenvalues of graph Laplacians via rank-one perturbations

We show how the spectrum of a graph Laplacian changes with respect to a certain type of rank-one perturbation. We apply our finding to give new short proofs of the spectral version of Kirchhoff's Matrix Tree Theorem and known derivations for the characteristic polynomials of the Laplacians for several well known families of graphs, including complete, complete multipartite, and threshold graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Linear algebraic techniques for spanning tree enumeration

Kirchhoff's Matrix-Tree Theorem asserts that the number of spanning trees in a finite graph can be computed from the determinant of any of its reduced Laplacian matrices. In many cases, even for well-studied families of graphs, this can be computationally or algebraically taxing. We show how two well-known results from linear algebra, the Matrix Determinant Lemma and the Schur complement, can be used to elegantly count the spanning trees in several significant families of graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Face enumeration on simplicial complexes

Let $M$ be a closed triangulable manifold, and let $Δ$ be a triangulation of $M$. What is the smallest number of vertices that $Δ$ can have? How big or small can the number of edges of $Δ$ be as a function of the number of vertices? More generally, what are the possible face numbers ($f$-numbers, for short) that $Δ$ can have? In other words, what restrictions does the topology of $M$ place on the possible $f$-numbers of triangulations of $M$? To make things even more interesting, we can add some combinatorial conditions on the triangulations we are considering (e.g., flagness, balancedness, etc.) and ask what additional restrictions these combinatorial conditions impose. While only a few theorems in this area of combinatorics were known a couple of decades ago, in the last ten years or so, the field simply exploded with new results and ideas. Thus we feel that a survey paper is long overdue. As new theorems are being proved while we are typing this chapter, and as we have only a limited number of pages, we apologize in advance to our friends and colleagues, some of whose results will not get mentioned here.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower Bound Theorems and a Generalized Lower Bound Conjecture for balanced simplicial complexes

A $(d-1)$-dimensional simplicial complex is called balanced if its underlying graph admits a proper $d$-coloring. We show that many well-known face enumeration results have natural balanced analogs (or at least conjectural analogs). Specifically, we prove the balanced analog of the celebrated Lower Bound Theorem for pseudomanifolds and characterize the case of equality; we introduce and characterize the balanced analog of the Walkup class; we propose the balanced analog of the Generalized Lower Bound Conjecture and establish some related results. We close with constructions of balanced manifolds with few vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Lexicographic shellability, matroids and pure order ideals

In 1977 Stanley conjectured that the $h$-vector of a matroid independence complex is a pure $O$-sequence. In this paper we use lexicographic shellability for matroids to motivate a combinatorial strengthening of Stanley's conjecture. This suggests that a pure $O$-sequence can be constructed from combinatorial data arising from the shelling. We then prove that our conjecture holds for matroids of rank at most four, settling the rank four case of Stanley's conjecture. In general, we prove that if our conjecture holds for all rank $d$ matroids on at most $2d$ elements, then it holds for all matroids.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A classification of the face numbers of Buchsbaum simplicial posets

The family of Buchsbaum simplicial posets generalizes the family of simplicial cell manifolds. The $h'$-vector of a simplicial complex or simplicial poset encodes the combinatorial and topological data of its face numbers and the reduced Betti numbers of its geometric realization. Novik and Swartz showed that the $h'$-vector of a Buchsbaum simplicial poset satisfies certain simple inequalities; in this paper we show that these necessary conditions are in fact sufficient to characterize the $h'$-vectors of Buchsbaum simplicial posets with prescribed Betti numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Combinatorial Markov chains on linear extensions

We consider generalizations of Schuetzenberger's promotion operator on the set L of linear extensions of a finite poset of size n. This gives rise to a strongly connected graph on L. By assigning weights to the edges of the graph in two different ways, we study two Markov chains, both of which are irreducible. The stationary state of one gives rise to the uniform distribution, whereas the weights of the stationary state of the other has a nice product formula. This generalizes results by Hendricks on the Tsetlin library, which corresponds to the case when the poset is the anti-chain and hence L=S_n is the full symmetric group. We also provide explicit eigenvalues of the transition matrix in general when the poset is a rooted forest. This is shown by proving that the associated monoid is R-trivial and then using Steinberg's extension of Brown's theory for Markov chains on left regular bands to R-trivial monoids.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Markov chains for promotion operators

We consider generalizations of Schuetzenberger's promotion operator on the set L of linear extensions of a finite poset. This gives rise to a strongly connected graph on L. In earlier work (arXiv:1205.7074), we studied promotion-based Markov chains on these linear extensions which generalizes results on the Tsetlin library. We used the theory of R-trivial monoids in an essential way to obtain explicitly the eigenvalues of the transition matrix in general when the poset is a rooted forest. We first survey these results and then present explicit bounds on the mixing time and conjecture eigenvalue formulas for more general posets. We also present a generalization of promotion to arbitrary subsets of the symmetric group.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The combinatorics of hyperbolized manifolds

A topological version of a longstanding conjecture of H. Hopf, originally proposed by W. Thurston, states that the sign of the Euler characteristic of a closed aspherical manifold of dimension $d=2m$ depends only on the parity of $m$. Gromov defined several hyperbolization functors which produce an aspherical manifold from a given simplicial or cubical manifold. We investigate the combinatorics of several of these hyperbolizations and verify the Euler Characteristic Sign Conjecture for each of them. In addition, we explore further combinatorial properties of these hyperbolizations as they relate to several well-studied generating functions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

From flag complexes to banner complexes

A notion of an $i$-banner simplicial complex is introduced. For various values of $i$, these complexes interpolate between the class of flag complexes and the class of all simplicial complexes. Examples of simplicial spheres of an arbitrary dimension that are $(i+1)$-banner but not $i$-banner are constructed. It is shown that several theorems for flag complexes have appropriate $i$-banner analogues. Among them are (1) the codimension-$(i+j-1)$ skeleton of an $i$-banner homology sphere $Δ$ is $2(i+j)$-Cohen--Macaulay for all $0\leq j\leq \dimΔ+1-i$, and (2) for every $i$-banner simplicial complex $Δ$ there exists a balanced complex $Γ$ with the same number of vertices as $Δ$ whose face numbers of dimension $i-1$ and higher coincide with those of $Δ$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Not all simplicial polytopes are weakly vertex-decomposable

In 1980 Provan and Billera defined the notion of weak $k$-decomposability for pure simplicial complexes. They showed the diameter of a weakly $k$-decomposable simplicial complex $Δ$ is bounded above by a polynomial function of the number of $k$-faces in $Δ$ and its dimension. For weakly 0-decomposable complexes, this bound is linear in the number of vertices and the dimension. In this paper we exhibit the first examples of non-weakly 0-decomposable simplicial polytopes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Cellular Resolutions of Ideals Defined by Simplicial Homomorphisms

In this paper we introduce the class of ordered homomorphism ideals and prove that these ideals admit minimal cellular resolutions constructed as homomorphism complexes. As a key ingredient of our work, we introduce the class of cointerval simplicial complexes and investigate their combinatorial and topological properties. As a concrete illustration of these structural results, we introduce and study nonnesting monomial ideals, an interesting family of combinatorially defined ideals.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Centrally symmetric manifolds with few vertices

A centrally symmetric $2d$-vertex combinatorial triangulation of the product of spheres $§^i\times§^{d-2-i}$ is constructed for all pairs of non-negative integers $i$ and $d$ with $0\leq i \leq d-2$. For the case of $i=d-2-i$, the existence of such a triangulation was conjectured by Sparla. The constructed complex admits a vertex-transitive action by a group of order $4d$. The crux of this construction is a definition of a certain full-dimensional subcomplex, $\B(i,d)$, of the boundary complex of the $d$-dimensional cross-polytope. This complex $\B(i,d)$ is a combinatorial manifold with boundary and its boundary provides a required triangulation of $§^i\times§^{d-i-2}$. Enumerative characteristics of $\B(i,d)$ and its boundary, and connections to another conjecture of Sparla are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Lower Bounds for Buchsbaum* Complexes

The class of $(d-1)$-dimensional Buchsbaum* simplicial complexes is studied. It is shown that the rank-selected subcomplexes of a (completely) balanced Buchsbaum* simplicial complex are also Buchsbaum*. Using this result, lower bounds on the $h$-numbers of balanced Buchsbaum* simplicial complexes are established. In addition, sharp lower bounds on the $h$-numbers of flag $m$-Buchsbaum* simplicial complexes are derived, and the case of equality is treated.

0 citations0 reviewsNo code linkedOpen access