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.     

A GKM description of the equivariant cohomology ring of a homogeneous space

Let T be a torus of dimension n > 1 and M a compact T-manifold. M is a GKM manifold if the set of zero dimensional orbits in the orbit space M/T is zero dimensional and the set of one dimensional orbits in M/T is one dimensional. For such a manifold these sets of orbits have the structure of a labelled graph and it is known that a lot of topological information about M is encoded in this graph. In this paper we prove that every compact homogeneous space M of non-zero Euler characteristic is of GKM type and show that the graph associated with M encodes geometric information about M as well as topological information. For example, from this graph one can detect whether M admits an invariant complex structure or an invariant almost complex structure.     

Cayley graphs having nice enumerations

LetW be the Cayley graph of an infinite finitely generated group andM be a finite cover ofW. It is proved in the paper thatTh(M) is finitely axiomatizable overW ifW has a nice enumeration (in the sense of G. Ahlbrandt and M. Ziegler). A finitely generated free abelian group provides such an example. It is shown that in the non-abelian case the corresponding examples are rather rate. In particular, in the soluble case they must be virtually abelian. We discuss the finite model property for finite covers of Cayley graphs of virtually abelian groups and the existence of nice enumerations for strongly minimal structures in general.     

One‐way infinite 2‐walks in planar graphs

We prove that every 3‐connected 2‐indivisible infinite planar graph has a 1‐way infinite 2‐walk. (A graph is 2‐indivisible if deleting finitely many vertices leaves at most one infinite component, and a 2‐walk is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1‐way infinite path.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

A Distributive Lattice on the Set of Perfect Matchings of a Plane Bipartite Graph

Let G be a plane bipartite graph and M(G) the set of perfect matchings of G. The Z-transformation graph of G is defined as a graph on M(G): M,MM(G) are joined by an edge if and only if they differ only in one cycle that is the boundary of an inner face of G. A property that a certain orientation of the Z-transformation graph of G is acyclic implies a partially ordered relation on M(G). An equivalent definition of the poset M(G) is discussed in detail. If G is elementary, the following main results are obtained in this article: the poset M(G) is a finite distributive lattice, and its Hasse diagram is isomorphic to the Z-transformation digraph of G. Further, a distributive lattice structure is established on the set of perfect matchings of any plane bipartite graph.     

On tree‐decompositions of one‐ended graphs

A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays.     

Schur multiplicators of infinite pro-<Emphasis Type="Italic">p</Emphasis>-groups with finite coclass

Let G be an infinite pro-p-group of finite coclass and let M(G) be its Schur multiplicator. For p > 2, we determine the isomorphism type of Hom(M(G), ℤ_p), where ℤ_p denotes the p-adic integers, and show that M(G) is infinite. For p = 2, we investigate the Schur multiplicators of the infinite pro-2-groups of small coclass and show that M(G) can be infinite, finite or even trivial.     

The Zariski Topology-Graph of Modules Over Commutative Rings

Let M be a module over a commutative ring, and let Spec(M) be the collection of all prime submodules of M. We topologize Spec(M) with Zariski topology, which is analogous to that for Spec(R), and for a nonempty subset T of Spec(M), we introduce a new graph G(τ _T ), called the Zariski topology-graph. This graph helps us to study the algebraic (resp. topological) properties of M (resp. Spec(M)) by using the graph theoretical tools.     

Colorings of infinite graphs without one-colored rays

The R-chromatic number of a graph G is the least number of subsets of vertices forming a partition of V(G), and which induce subgraphs of G without infinite paths. For any integer n ≥ 2, we give sufficient conditions for a graph containing no subdivision of an infinite complete graph to have a R-chromatic number ≤ n. © 1996 John Wiley & Sons, Inc.     

Mutation of Auslander Generators for Selfinjective Algebras

Let Λ be an artin algebra with representation dimension equal to three and M an Auslander generator of Λ. We show how, under certain assumptions, we can mutate M to get a new Auslander generator whose endomorphism ring is derived equivalent to the endomorphism ring of M. We apply our results to selfinjective algebras with radical cube zero of infinite representation type, where we construct an infinite set of Auslander generators.     

Generalized Thrackle Drawings of Non-bipartite Graphs

A graph drawing is called a generalized thrackle if every pair of edges meets an odd number of times. In a previous paper, we showed that a bipartite graph G can be drawn as a generalized thrackle on an oriented closed surface M if and only if G can be embedded in M. In this paper, we use Lins’ notion of a parity embedding and show that a non-bipartite graph can be drawn as a generalized thrackle on an oriented closed surface M if and only if there is a parity embedding of G in a closed non-orientable surface of Euler characteristic χ(M)−1. As a corollary, we prove a sharp upper bound for the number of edges of a simple generalized thrackle.     

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

An Excluded-Minor Problem in Matroids

Consider the class of matroids M with the property that M is not isomorphic to a wheel graph, but has an element e such that both M\e and M/e are isomorphic to a series-parallel extension of a wheel graph. We give a constructive characterization of such matroids by determining explicitly the 3-connected members of the class. We also relate this problem with excluded minor problems.Received May 30, 2003     

On the maximal order of cyclicity of antisymmetric directed graphs

A directed graph G without loops or multiple edges is said to be antisymmetric if for each pair of distinct vertices of G (say u and v), G contains at most one of the two possible directed edges with end-vertices u and v. In this paper we study edge-sets M of an antisymmetric graph G with the following extremal property: By deleting all edges of M from G we obtain an acyclic graph, but by deleting from G all edges of M except one arbitrary edge, we always obtain a graph containing a cycle. It is proved (in Theorem 1) that if M has the above mentioned property, then the replacing of each edge of M in G by an edge with the opposite direction has the same effect as deletion: the graph obtained is acyclic. Further we study the order of cyclicity of G (= theminimalnumberofedgesinsuchasetM) and the maximal order of cyclicity in an antisymmetric graph with given number n of vertices. It is shown that for n < 10 this number is equal to the maximal number of edge-disjoint circuits in the complete (undirected) graph with n vertices and for n = 10 (and for an infinite set of n's) the first number is greater than the latter.     

Fields interpretable in rosy theories

We are working in a monster model ℭ of a rosy theory T. We prove the following theorems, generalizing the appropriate results from the finite Morley rank case and o-minimal structures. If R is a ⋁-definable integral domain of positive, finite U^t-rank, then its field of fractions is interpretable in ℭ. If A and M are infinite, definable, abelian groups such that A acts definably and faithfully on M as a group of automorphisms, M is A-minimal and U^t(M) is finite, then there is an infinite field interpretable in ℭ. If G is an infinite, solvable but non nilpotent-by-finite, definable group of finite U^t-rank and T has NIP, then there is an infinite field interpretable in 〈G, ·〉.     

Infinite paths in planar graphs III, 1‐way infinite paths

An infinite graph is 2‐indivisible if the deletion of any finite set of vertices from the graph results in exactly one infinite component. Let G be a 4‐connected, 2‐indivisible, infinite, plane graph. It is known that G contains a spanning 1‐way infinite path. In this paper, we prove a stronger result by showing that, for any vertex x and any edge e on a facial cycle of G, there is a spanning 1‐way infinite path in G from x and through e. Results will be used in two forthcoming papers to establish a conjecture of Nash‐Williams. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

On the Cocircuit Graph of an Oriented Matroid

In this paper we consider the cocircuit graph G _M of an oriented matroid M , the 1 -skeleton of the cell complex W formed by the span of the cocircuits of M . In general, W is not determined by G _M . However, we show that if the vertex set (resp. edge set) of G _M is properly labeled by the hyperplanes (resp. colines) of M , G _M determines W . Also we prove that, when M is uniform, the cocircuit graph together with all antipodal pairs of vertices being marked determines W . These results can be considered as variations of Blind—Mani's theorem that says the 1-skeleton of a simple convex polytope determines its face lattice. Received August 14, 1998, and in revised form March 2, 1999.