Universal coverings of PL-manifolds via coloured graphs

Summary By means of techniques and results concerning maps on surfaces [JS] and edge-coloured graphs representing PL-manifolds [FGG], we prove the existence of an infinite ball complexP(n), n > 1, such thatevery orientable PL-manifold of dimension n is a quotient of |P(n)| by the action of a finite index subgroup of a Fuchsian group with signature ,with h(2) = h(3) = 4 and h(n) = 2, for n > 3. The core of the proof is that all orientable PL-manifolds of dimensionn can be represented by edge-coloured graphs which are quotients of a universal graph, only depending onn.     

Hom complexes and hypergraph colorings

Babson and Kozlov (2006) [2] studied Hom-complexes of graphs with a focus on graph colorings. In this paper, we generalize Hom-complexes to r-uniform hypergraphs (with multiplicities) and study them mainly in connection with hypergraph colorings. We reinterpret a result of Alon, Frankl and Lovász (1986) [1] by Hom-complexes and show a hierarchy of known lower bounds for the chromatic numbers of r-uniform hypergraphs (with multiplicities) using Hom-complexes.     

Barycentric systems and stretchability

Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least three free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.     

The Locally Connected Compact Metric Spaces Embeddable In The Plane

We prove that a 2-connected, locally connected, compact topological space M is homeomorphic to a subset of the 2-sphere if and only if M is metrizable and contains none of the Kuratowski graphs K ₅ and K _3,3.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

Star clusters in independence complexes of graphs

We introduce the notion of star cluster of a simplex in a simplicial complex. This concept provides a general tool to study the topology of independence complexes of graphs. We use star clusters to answer a question arisen from works of Engström and Jonsson on the homotopy type of independence complexes of triangle-free graphs and to investigate a large number of examples which appear in the literature. We present an alternative way to study the chromatic and clique numbers of a graph from a homotopical point of view and obtain new results regarding the connectivity of independence complexes.     

On the vertex group of n-manifolds

In this paper we obtain the decomposition of the vertex group of n-manifolds, extending the one given by Kauffman and Lins for dimension 3 and solving the related conjecture. The result is obtained in the more general category of gems: the vertex group of a gem , representing an n-manifold M, is the free product of n copies of the fundamental group of M and a free group F of rank N–n, where N is the number of n-residues of . In particular, for crystallizations FZ and consequently the vertex group is an invariant of M.     

Classification Of Locally 2-Connected Compact Metric Spaces

The aim of this paper is to prove that, for compact metric spaces which do not contain infinite complete graphs, the (strong) property of being locally 2-dimensional is guaranteed just by a (weak) local connectivity condition. Specifically, we prove that a locally 2-connected, compact metric space M either contains an infinite complete graph or is surface like in the following sense: There exists a unique surface S such that S and M contain the same finite graphs. Moreover, M is embeddable in S, that is, M is homeomorphic to a subset of S.     

The asymptotic behaviour of the number of three-connected triangulations of the disk,with a reflective symmetry in a line

We consider the enumeration of the three-connected triangulations of the disk, with a reflective symmetry about a line. The asymptotic behavior is unlike that observed for rooted maps or for maps having rotational symmetry.     

Lie algebras and the Four Color Theorem

We present a statement about Lie algebras that is equivalent to the Four Color Theorem.     

Lower Bounds in Minimum Rank Problems

The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.     

Computing the genus of the 2-amalgamations of graphs

The above authors [2] and S. Stahl [3] have shown that if a graphG is the 2-amalgamation of subgraphsG ₁ andG ₂ (namely ifG=G ₁∪G ₂ andG ₁∩G ₂={x, y}, two distinct points) then the orientable genus ofG,γ(G), is given byγ(G)=γ(G ₁)+γ(G ₂)+ε, whereε=0,1 or −1. In this paper we sharpen that result by giving a means by whichε may be computed exactly. This result is then used to give two irreducible graphs for each orientable surface.     

Geodetic blocks of diameter three

It is shown that geodetic blocks of diameter 3 are self-centred and upper and lower geodetic critical and also lower diameter critical. Geodetic blocks of diameter 3 which are isomorphic toK _n ⁽²⁾ are characterised. The second author is on leave from the A. M. Jain College, Madras and acknowledges the financial support of the U. G. C. Teacher Fellowship for this research.     

Colouring games based on autotopisms of Latin hyper-rectangles

Abstract

Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Θ-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Θ of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.     

The Betti numbers of some finite racks

We show that the lower bounds for Betti numbers given in (J. Pure Appl. Algebra 157 (2001) 135) are equalities for a class of racks that includes dihedral and Alexander racks. We confirm a conjecture from the same paper by defining a splitting for the short exact sequence of quandle chain complexes. We define isomorphisms between Alexander racks of certain forms, and we also list the second and third homology groups of some dihedral and Alexander quandles.     

A characterization of planar graphs by trémaux orders

A new characterization of planar graphs is stated in terms of an order relation on the vertices, called the Trémaux order, associated with any Trémaux spanning tree or Depth-First-Search Tree. The proof relies on the work of W. T. Tutte on the theory of crossings and the Trémaux algebraic theory of planarity developed by P. Rosenstiehl.     

An effective algorithm to get linking numbers of 3-manifolds

Summary A colored triangulation of a 3-manifoldM ³ is a decomposition into tetrahedra so that each vertex of them receive one of the colors 0, 1, 2, 3 in such a way that each tetrahedron has four differently colored vertices. From the combinatorics of the dual of a colored triangulation forM ³ we provide an easy algorithm to get a special kind of intersection matrix; from this matrix and from the torsion coefficients of the firstZ-homology group ofM ³ we provide a formula which yields its linking numbers.     

On fundamental groups of quotient spaces

In classical covering space theory, a covering map induces an injection of fundamental groups. This paper reveals a dual property for certain quotient maps having connected fibers, with applications to orbit spaces of vector fields and leaf spaces in general.     

On the structure of Hom quandles

We continue the study of the quandle of homomorphisms into a medial quandle begun in [1]. We show that it suffices to consider only medial source quandles, and therefore the structure theorem of [10] provides a characterization of the Hom quandle. In the particular case when the target is 2-reductive this characterization takes on a simple form that makes it easy to count and determine the structure of the Hom quandle.