Kuratowski's and Wagner's theorems for matroids

In an earlier paper we proved the following theorem, which provides a strengthening of Tutte's well-known characterization of regular (totally unimodular) matroids: A binary matroid is regular if it does not have the Fano matroid or its dual as a series-minor (parallel-minor). In this paper we prove two theorems (Theorems 5.1 and 6.1) which provide the same kind of strengthening for Tutte's characterization of the graphic matroids (i.e., bond-matroids). One interesting aspect of these theorems is the introduction of the matroids of “type R”. It turns out that these matroids are, in at least two different senses, the smallest regular matroids which are neither graphic nor cographic (Theorems 6.2 and 6.3).     

Intersection theory for graphs

An intersection theory developed by the author for matroids embedded in uniform geometries is applied to the case when the ambient geometry is the lattice of partitions of a finite set so that the matroid is a graph. General embedding theorems when applied to graphs give new interpretations to such invariants as the dichromate of Tutte. A polynomial in n + 1 variables, the polychromate, is defined for graphs with n vertices. This invariant is shown to be strictly stronger than the dichromate, it is edge-reconstructible and can be calculated for proper graphs from the polychromate of the complementary graph. By using Tutte's construction for codichromatic graphs (J. Combinatorial Theory 16 (1974), 168–174), copolychromatic (and therefore codichromatic) graphs of arbitrarily high connectivity are constructed thereby solving a problem posed in Tutte's paper.     

A characterization of complete matroid base graphs

This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form K_n × K_m for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs.     

Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.     

Combinatorially homogeneous graphs

Gardiner classified ultrahomogeneous graphs and posed the problem of defining “combinatorial homogeneity”. Later, Ronse proved that homogeneous graphs are ultrahomogeneous by classifying such graphs. In this paper, we give a direct proof that (suitably defined) combinatorially homogeneous graphs are ultrahomogeneous. Also, we clasify combinatorially C-homogeneous graphs.     

Subgraphs as circuits and bases of matroids

As is well known, the cycles of any given graph G may be regarded as the circuits of a matroid defined on the edge set of G. The question of whether other families of connected graphs exist such that, given any graph G, the subgraphs of G isomorphic to some member of the family may be regarded as the circuits of a matroid defined on the edge set of G led us, in two other papers, to the proof of some results concerning properties of the cycles when regarded as circuits of such matroids. Here we prove that the wheels share many of these properties with the cycles. Moreover, properties of subgraphs which may be regarded as bases of such matroids are also investigated.     

A class of solutions to the gossip problem,part I

We characterize optimal solutions to the gossip problem in which no one hears his own information. That is, we consider graphs on n vertices where the edges are given a linear ordering such that an increasing path exists from each vertex to every other, but there is no increasing path from a vertex to itself. Such graphs exist if and only if n is even, in which case the fewest number of edges is 2n - 4, as in the original gossip problem (in which the “$\text{N}$o $\text{O}$ne $\text{H}$ears his $\text{O}$wn information” condition did not appear). We characterize optimal solutions of this sort, called NOHO-graphs, by a correspondence with quadruples consisting of two permutations and two binary sequences. The correspondence uses a canonical numbering of the vertices of the graph; it arises from the edge ordering. (Exception: there are two optimal solution graphs which do not meet this characterization.) Also in Part I, we show constructively that NOHO-graphs are Hamiltonian, bipartite, and planar. In Part II, we study other properties of the associated quadruples, which includes enumerating them. In Part III, we enumerate the non-isomorphic NOHO-graphs.     

Connectivity in bicircular matroids

Tutte has defined n-connection for matroids and proved a connected graph is n-connected if and only if its polygon matroid is n-connected. In this paper we introduce a new notion of connection in graphs, called n-biconnection, and prove an analogous theorem for graphs and their bicircular matroids. Results concerning 3-biconnected graphs are also presented.     

The uniquely embeddable planar graphs

Whitney [7] proved in 1932 that for any two embeddings of a planar 3-connected graph, their combinatorial duals are isomorphic. In this manner, the term “uniquely embeddable planar graph” was introduced. It is a well-known fact that combinatorial and geometrical duals are equivalent concepts. In this paper, the concept of unique embeddability is introduced in terms of special types of isomorphisms between any two embeddings of a planar graph. From this, the class U of all graphs which are uniquely embeddable in the plane according to this definition, is determined, and the planar 3-connected graphs are a proper subset of U. It turns out that the graphs in U have a unique geometrical dual (i.e., for any two embeddings of such a graph, their geometrical duals are isomorphic). Furthermore, the theorems and their proofs do not involve any type of duals.     

On a classification of independence systems

By generalizing matroid axiomatics we provide a framework in which independence systems may be classified. The concept is applied to independence systems arising from well known combinatorial optimization problems such as k-matroid intersection, matchoid, vertex packing in finite graphs and travelling salesman problems.     

Ear-decompositions of matching-covered graphs

We call a graphmatching-covered if every line belongs to a perfect matching. We study the technique of “ear-decompositions” of such graphs. We prove that a non-bipartite matching-covered graph containsK ₄ orK ₂⊕K ₃ (the triangular prism). Using this result, we give new characterizations of those graphs whose matching and covering numbers are equal. We apply these results to the theory of τ-critical graphs.     

Proofs as bearers of mathematical knowledge

Yehuda Rav’s inspiring paper “Why do we prove theorems?” published in Philosophia Mathematica (1999, 7, pp. 5–41) has interesting implications for mathematics education. We examine Rav’s central ideas on proof—that proofs convey important elements of mathematics such as strategies and methods, that it is “proofs rather than theorems that are the bearers of mathematical knowledge”and thus that proofs should be the primary focus of mathematical interest—and then discuss their significance for mathematics education in general and for the teaching of proof in particular.     

The enumeration of irreducible combinatorial objects

A unique factorization theory for labelled combinatorial objects is developed and applied to enumerate several families of objects, including certain families of set partitions, permutations, graphs, and collections of subintervals of [1, n]. The theory involves a notion of irreducibility with respect to set partitions and the enumeration formulas that arise result from a generalization of the well-known “exponential formula.”     

Circuit preserving edge maps II

In Section 1 of this article we prove the following. Let f: G → G′ be a circuit surjection, i.e., a mapping of the edge set of G onto the edge set of G′ which maps circuits of G onto circuits of G′, where G, G′ are graphs without loops or multiple edges and G′ has no isolated vertices. We show that if G is assumed finite and 3-connected, then f is induced by a vertex isomorphism. If G is assumed 3-connected but not necessarily finite and G′ is assumed to not be a circuit, then f is induced by a vertex isomorphism. Examples of circuit surjections f: G → G′ where G′ is a circuit and G is an infinite graph of arbitrarily large connectivity are given. In general if we assume G two-connected and G′ not a circuit then any circuit surjection f: G → G′ may be written as the composite of three maps, f(G) = q(h(k(G))), where k is a 1-1 onto edge map which preserves circuits in both directions (the “2-isomorphism” of Whitney (Amer. J. Math. 55 (1933), 245–254) when G is finite), h is an onto edge map obtained by replacing “suspended chains” of k(G) with single edges, and G is a circuit injection (a 1-1 circuit surjection). Let f: G → M be a 1-1 onto mapping of the edges of G onto the cells of M which takes circuits of G onto circuits of M where G is a graph with no isolated vertices, M a matroid. If there exists a circuit C of M which is not the image of a circuit in G, we call f nontrivial, otherwise trivial. In Section 2 we show the following. Let G be a graph of even order. Then the statement “no trivial map f: G → M exists, where M is a binary matroid,” is equivalent to “G is Hamiltonian.” If G is a graph of odd order, then the statement “no nontrivial map f: G → M exists, where M is a binary matroid” is equivalent to “G is almost Hamiltonian,” where we define a graph G of order n to be almost Hamiltonian if every subset of vertices of order n − 1 is contained in some circuit of G.     

A quantifier for matroid duality

A quantifier is introduced on the elements of a matroid which, given an element e, says “for all elements (except possibly e) of some circuit containing e,…”. The matroid dual of this quantifier is shown to be identical with its logical dual, and this provides an elegant reformulation of Minty's self-dual axiomatization of matroids.This approach also provides a practical, and in a sense optimal, means of taking a statement in terms of circuits and constructing its dual, still in terms of circuits.     

Branch decomposition heuristics for linear matroids

This paper presents three new heuristics which utilize classification, max-flow, and matroid intersection algorithms respectively to derive near-optimal branch decompositions for linear matroids. In the literature, there are already excellent heuristics for graphs, however, no practical branch decomposition methods for general linear matroids have been addressed yet. Introducing a “measure” which compares the “similarity” of elements of a linear matroid, this work reforms the linear matroid into a similarity graph. Then, the classification method, the max-flow method, and the mat-flow method, all based on the similarity graph, are utilized on the similarity graph to derive separations for a near-optimal branch decomposition. Computational results using the methods on linear matroid instances are shown respectively.     

Graph congruences and what they connote

Abstract

The algebraic notion of a “congruence” seems to be foreign to contemporary graph theory. We propound that it need not be so by developing a theory of congruences of graphs: a congruence on a graph G = (V, E) being a pair (～, ) of which ～ is an equivalence relation on V and is a set of unordered pairs of vertices of G with a special relationship to ～ and E. Kernels and quotient structures are used in this theory to develop homomorphism and isomorphism theorems which remind one of similar results in an algebraic context. We show that this theory can be applied to deliver structural decompositions of graphs into “factor” graphs having very special properties, such as the result that each graph, except one, is a subdirect product of graphs with universal vertices. In a final section, we discuss corresponding concepts and briefly describe a corresponding theory for graphs which have a loop at every vertex and which we call loopy graphs. They are in a sense more “algebraic” than simple graphs, with their meet-semilattices of all congruences becoming complete algebraic lattices.     

Oriented matroids and multiply ordered sets

The many different axiomatizations for matroids all have their uses. In this paper we show that Gutierrez Novoa's n-ordered sets are cryptomorphically the same as the oriented matroids, thereby establishing the existence of an axiomatization for oriented matroids in which the “oriented” bases of the matroid are the objects of paramount importance.     

Generating quadrangulations of surfaces with minimum degree at least 3

In this article, we show that all quadrangulations of the sphere with minimum degree at least 3 can be constructed from the pseudo‐double wheels, preserving the minimum degree at least 3, by a sequence of two kinds of transformations called “vertex‐splitting” and “4‐cycle addition.” We also consider such generating theorems for other closed surfaces. These theorems can be translated into those of 4‐regular graphs on surfaces by taking duals. © 1999 John Wiley & Sons, In. J Graph Theory 30: 223–234, 1999     

The fuzzy tychonoff theorem

Much of topology can be done in a setting where open sets have “fuzzy boundaries.” To render this precise, the paper first describes cl_∞-monoids, which are used to measure the degree of membership of points in sets. Then L- or “fuzzy” sets are defined, and suitable collections of these are called L-topological spaces. A number of examples and results for such spaces are given. Perhaps most interesting is a version of the Tychonoff theorem which gives necessary and sufficient conditions on L for all collections with given cardinality of compact L-spaces to have compact product.