The Geometry of Relations

The classical way to study a finite poset (X, ≤ ) using topology is by means of the simplicial complex Δ _X of its nonempty chains. There is also an alternative approach, regarding X as a finite topological space. In this article we introduce new constructions for studying X topologically: inspired by a classical paper of Dowker (Ann Math 56:84–95, 1952), we define the simplicial complexes K _X and L _X associated to the relation ≤. In many cases these polyhedra have the same homotopy type as the order complex Δ _X . We give a complete characterization of the simplicial complexes that are the K or L-complexes of some finite poset and prove that K _X and L _X are topologically equivalent to the smaller complexes K′ _X , L′ _X induced by the relation <. More precisely, we prove that K _X (resp. L _X ) simplicially collapses to K′ _X (resp. L′ _X ). The paper concludes with a result that relates the K-complexes of two posets X, Y with closed relations R ⊂ X × Y.     

On Homotopy Types of Alexandroff Spaces

We generalise some results of R. E. Stong concerning finite spaces to wider subclasses of Alexandroff spaces. In particular, we characterize pairs of spaces X,Y such that the compact-open topology on C(X,Y) is Alexandroff, give a homotopy type classification of a class of infinite Alexandroff spaces and prove some results concerning cores of locally finite spaces. We also discuss a mistake found in an article of F.G. Arenas. Since the category of T ₀ Alexandroff spaces is equivalent to the category of posets, our results may lead to a deeper understanding of the notion of a core of an infinite poset.     

The universality of Hom complexes of graphs

It is shown that given a connected graph T with at least one edge and an arbitrary finite simplicial complex X, there is a graph G such that the complex Hom(T,G) is homotopy equivalent to X. The proof is constructive, and uses a nerve lemma. Along the way several results regarding Hom complexes, exponentials of graphs, and subdivisions are established that may be of independent interest.     

Cores of Simplicial Complexes

We introduce a method to reduce the study of the topology of a simplicial complex to that of a simpler one. Applying this method to complexes arising from graphs, we give topological meaning to classical graph invariants. As a consequence, we answer some questions raised in (Ehrenborg and Hetyei in Eur. J. Comb. 27(6):906–923, 2006) on the independence complex and the dominance complex of a forest and obtain improved algorithms to compute their homotopy types.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Order-Compactifications of Totally Ordered Spaces: Revisited

Order-compactifications of totally ordered spaces were described by Blatter (J Approx Theory 13:56–65, 1975) and by Kent and Richmond (J Math Math Sci 11(4):683–694, 1988). Their results generalize a similar characterization of order-compactifications of linearly ordered spaces, obtained independently by Fedorčuk (Soviet Math Dokl 7:1011–1014, 1966; Sib Math J 10:124–132, 1969) and Kaufman (Colloq Math 17:35–39, 1967). In this note we give a simple characterization of the topology of a totally ordered space, as well as give a new simplified proof of the main results of Blatter (J Approx Theory 13:56–65, 1975) and Kent and Richmond (J Math Math Sci 11(4):683–694, 1988). Our main tool will be an order-topological modification of the Dedekind-MacNeille completion. In addition, for a zero-dimensional totally ordered space X, we determine which order-compactifications of X are Priestley order-compactifications.     

On the poset of conjugacy classes of subgroups of π-power index

We investigate tile poset S^π(G)/G of conjugacy clases of subgroups of π-power index in a finite group G. In particular, we are concerned with combinatorial and topological properties of the order complex of S^π(G)/G. We show that the order complex of S^π(G)/G iS homotopic to a join of orbit spaces of order complexes of posets, which bear structural information on the cheif factors of the group. Moreover, for π-solvable groups and in case π = {p} we reveal a shellable subposer of S^π(G)/G of the same homotopy type. This complements the study of the poset S^π(G) of subgroups of π-power index performed in [20]. For the analysis of the order complexes we develop some new lemmata on the topology of order complexes of posets and in the theory of shellability.     

Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.     

Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

On the derived category of a regular toric scheme

Let X be a quasi-compact scheme, equipped with an open covering by affine schemes U _σ = Spec A ^σ . A quasi-coherent sheaf on X gives rise, by taking sections over the U _σ , to a diagram of modules over the coordinate rings A ^σ , indexed by the intersection poset Σ of the covering. If X is a regular toric scheme over an arbitrary commutative ring, we prove that the unbounded derived category of quasi-coherent sheaves on X can be obtained from a category of Σ^op-diagrams of chain complexes of modules by inverting maps which induce homology isomorphisms on hyper-derived inverse limits. Moreover, we show that there is a finite set of weak generators, one for each cone in the fan Σ. The approach taken uses the machinery of Bousfield–Hirschhorn colocalisation of model categories. The first step is to characterise colocal objects; these turn out to be homotopy sheaves in the sense that chain complexes over different open sets U _σ agree on intersections up to quasi-isomorphism. In a second step it is shown that the homotopy category of homotopy sheaves is equivalent to the derived category of X.     

Higher order mixing and rigidity of algebraic actions on compact Abelian groups

Let Γ be a discrete group and fori=1,2; letα _i be an action of Γ on a compact abelian groupX _i by continuous automorphisms ofX _i. We study measurable equivariant mapsf: (X ₁,α ₁)→(X ₂,α ₂), and prove a rigidity result under certain assumption on the order of mixing of the underlying actions.     

Posets admitting a unique order-compatible topology

A characterization is given for those posets (X, ?) such that X admits exactly one topology inducing the given partial order ?. As a corollary, a poset is finite if and only if it is finite-dimensional and admits a unique compatible topology. Related applications and examples are also developed.     

Hom complexes and homotopy in the category of graphs

In this extended abstract we develop a notion of ×-homotopy of graph maps that is based on the internal hom associated to the categorical product. We show that graph ×-homotopy is characterized by the topological properties of the so-called Hom complex, a functorial way to assign a poset to a pair of graphs. Along the way we establish some structural properties of Hom complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. We end with a discussion of graph homotopies arising from other internal homs, including the construction of ‘A-theory’ associated to the cartesian product in the category of reflexive graphs. For proofs and further discussions we refer the reader to the full paper [Anton Dochtermann. Hom complexes and homotopy theory in the category of graphs. arXiv:math.CO/0605275].     

Quotient spaces determined by algebras of continuous functions

We prove that if X is a locally compact σ-compact space, then on its quotient, γ(X) say, determined by the algebra of all real valued bounded continuous functions on X, the quotient topology and the completely regular topology defined by this algebra are equal. It follows from this that if X is second countable locally compact, then γ(X) is second countable locally compact Hausdorff if and only if it is first countable. The interest in these results originated in [1] and [7] where the primitive ideal space of a C*-algebra was considered.     

A structure theorem for boundary-transitive graphs with infinitely many ends

We prove a structure theorem for locally finite connected graphsX with infinitely many ends admitting a non-compact group of automorphisms which is transitive in its action on the space of ends, Ω _X . For such a graphX, there is a uniquely determined biregular treeT (with both valencies finite), a continuous representationφ : Aut(X) → Aut(T) with compact kernel, an equivariant homeomorphism λ : Ω _X → Ω _T , and an equivariant map τ : Vert(X) → Vert(T) with finite fibers. Boundary-transitive trees are described, and some methods of constructing boundary-transitive graphs are discussed, as well as some examples.     

Torus graphs and simplicial posets

For several important classes of manifolds acted on by the torus, the information about the action can be encoded combinatorially by a regular n-valent graph with vector labels on its edges, which we refer to as the torus graph. By analogy with the GKM-graphs, we introduce the notion of equivariant cohomology of a torus graph, and show that it is isomorphic to the face ring of the associated simplicial poset. This extends a series of previous results on the equivariant cohomology of torus manifolds. As a primary combinatorial application, we show that a simplicial poset is Cohen-Macaulay if its face ring is Cohen-Macaulay. This completes the algebraic characterisation of Cohen-Macaulay posets initiated by Stanley. We also study blow-ups of torus graphs and manifolds from both the algebraic and the topological points of view.     

Group Representations with Empty Residual Spectrum

Let X be a Banach space on which a discrete group Γ acts by isometries. For certain natural choices of X, every element of the group algebra, when regarded as an operator on X, has empty residual spectrum. We show, for instance, that this occurs if X is ℓ ²(Γ) or the group von Neumann algebra VN(Γ). In our approach, we introduce the notion of a surjunctive pair, and develop some of the basic properties of this construction. The cases X = ℓ ^p (Γ) for 1 ≤ p < 2 or 2 < p < ∞ are more difficult. If Γ is amenable we can obtain partial results, using a majorization result of Herz; an example of Willis shows that some condition on Γ is necessary.     

Distinguishing labeling of the actions of almost simple groups

Suppose Γ is a group acting on a set X, written as (Γ,X). An r-labeling f: X→{1,2, ..., r} of X is called distinguishing for (Γ,X) if for all σ∈Γ,σ≠1, there exists an element x∈X such that f(x)≠f(x ^σ ). The distinguishing number d(Γ,X) of (Γ,X) is the minimum r for which there is a distinguishing r-labeling for (Γ,X). If Γ is the automorphism group of a graph G, then d(Γ,V (G)) is denoted by d(G), and is called the distinguishing number of the graph G. The distinguishing set of Γ-actions is defined to be D*(Γ)={d(Γ,X): Γ acts on X}, and the distinguishing set of Γ-graphs is defined to be D(Γ)={d(G): Aut(G)≅Γ}. This paper determines the distinguishing set of Γ-actions and the distinguishing set of Γ-graphs for almost simple groups Γ.     

On based-free actions of compact lie groups on the hilbert cube

It is proved that a based-free action α of a given compact Lie groupG on the Hilbert cubeQ is equivalent to the standard based-free action σ if and only if the orbit spaceQ ₀/α of the free partQ ₀=Q* is aQ-manifold having the proper homotopy type of the orbit spaceQ ₀/σ. The existence of an equivariant retraction (Q ₀, σ)→(Q ₀, α) is established. It is proved that for any TikhonovG-spaceX the family of all equivariant mapsX→ conG separates the points and the closed sets inX. Translated fromMatematicheskie Zametki, Vol. 65, No. 2, pp. 163–174, February, 1999.