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.     

Construction of matroidal families by partly closed sets

A matroidal family of graphs is a set $\text{M}$≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of $\text{M}$ are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n?0, ?2n<r?1, n, $\text{r∈}\text{Z}$, the set $\text{M}\text{(n, r)={G∣G}$ is a graph with β(G)=nα(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of $\text{M}\text{(n, r)}$, s?r, we are able to give sufficient and necessary conditions for a subset $\text{P}\text{(n, r)}$ of $\text{M}\text{(n, r)}$ to yield a matroidal family of graphs when joined with the set $\text{I}\text{(n, s)}$ of all graphs $\text{G∈}\text{M}\text{(n, s)}$ which satisfy: If $\text{H∈}\text{P}\text{(n, r)}$, then H?G. In particular, it is shown that $\text{M}\text{(n, r)}$ is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, $\text{r∈}\text{Z}$, the set of bipartite elements of $\text{M}\text{(n, r)}$ can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1).     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

On a general class of graph polynomials

Let $\text{F}$ be a family of connected graphs. With each element α ∈ $\text{F}$, we can associate a weight w_α. Let G be a graph. An F-cover of G is a spanning subgraph of G in which every component belongs to $\text{F}$. With every F-cover we can associate a monomial π(C) = Π_αw_α, where the product is taken over all components of the cover. The F-polynomial of G is Σπ(C), where the sum is taken over all F-covers in G. We obtain general results for the complete graph and complete bipartite graphs, and we show that many of the well-known graph polynomials are special cases of more general F-polynomials.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Abelian extensions of topological vector groups

The possibility of endowing an Abelian topological group G with the structure of a topological vector space when a subgroup F of G and the quotient group $\text{G}\text{F}$ are topological vector groups is investigated. It is shown that, if F is a real Fréchet group and $\text{G}\text{F}$ a complete metrizable real vector group, then G is a complete metrizable real vector group. This result is of particular interest if $\text{G}\text{F}$ is finite dimensional or if F is one dimensional and $\text{G}\text{F}$ a separable Hilbert group.     

Uniqueness and faithfulness of embedding of toroidal graphs

A topological generalization of the uniqueness of duals of 3-connected planar graphs will be obtained. A graph G is uniquely embeddable in a surface F if for any two embeddings $\text{?}{}_1$, $\text{?}{}_2\text{:G → F}$, there are an autohomeomorphism h:F → F and an automorphism σ:G → G such that $\text{h°?}{}_1\text{= ?}{}_2\text{°σ}$. A graph G is faithfully embedabble in a surface F if there is an embedding $\text{?:G → F}$ such that for any automorphism σ:G → G, there is an autohomeomorphism h:F → F with $\text{h°? = f°σ}$. Our main theorems state that any 6-connected toroidal graph is uniquelly embeddable in a torus and that any 6-connected toroidal graph with precisely three exceptions is faithfully embeddable in a torus. The proofs are based on a classification of 6-regular torus graphs.     

On the rational spectra of graphs with abelian singer groups

Let G be a finite abelian group. We investigate those graphs $\text{G}$ admitting G as a sharply 1-transitive automorphism group and all of whose eigenvalues are rational. The study is made via the rational algebra $\text{P}$(G) of rational matrices with rational eigenvalues commuting with the regular matrix representation of G. In comparing the spectra obtainable for graphs in $\text{P}$(G) for various G's, we relate subschemes of a related association scheme, subalgebras of $\text{P}$(G), and the lattice of subgroups of G. One conclusion is that if the order of G is fifth-power-free, any graph with rational eigenvalues admitting G has a cospectral mate admitting the abelian group of the same order with prime-order elementary divisors.     

A note on the similarity depth

In this note we demonstrate the existence of E0L forms F and G which are n-similar, i.e. $\text{L}$ⁿ(F) = $\text{L}$ⁿ(G) but $\text{L}$ⁿ⁺¹(F)≠$\text{L}$ⁿ⁺¹(G) for n ∈ {2, 3}. This partially solves an open problem from [3].     

On the minimum number of disjoint pairs in a family of finite sets

The following conjecture of Katona is proved. Let X be a finite set of cardinality n, 1 ? m ? 2ⁿ. Then there is a family $\text{F}$, |$\text{F}$| = m, such that F ∈ $\text{F}$, G ? X, | G | > | F | implies G ∈ $\text{F}$ and $\text{F}$ minimizes the number of pairs (F₁, F₂), F₁, F₂ ∈ $\text{F}$ F₁ ∩ F₂ = ? over all families consisting of m subsets of X.     

Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

Left mean-ergodicity,fixed points,and invariant means

Recently Lau [15] generalized a result of Yeadon [25]. In the present paper we generalize Yeadon's result in another direction recasting it as a theorem of ergodic type. We call the notion of ergodicity required left mean-ergodicity and show how it relates to the mean-ergodicity of Nagel [21]. Connections with the existence of invariant means on spaces of continuous functions on semitopological semigroups S are made, connections concerning, among other things, a fixed point theorem of Mitchell [20] and Schwartz's property P of W¹-algebras [22]. For example, if $\text{M}$(S) is a certain subspace of C(S) (which was considered by Mitchell and is of almost periodic type, i.e., the right translates of a member of $\text{M}$(S) satisfy a compactness condition), then the assumption that $\text{M}$(S) has a left invariant mean is equivalent to the assumption that every representation of S of a certain kind by operators on a linear topological space X is left mean-ergodic. An analog involving the existence of a (left and right) invariant mean on $\text{M}$(S) is given, and we show our methods restrict in the Banach space setting to give short direct proofs of some results in [4], results involving the existence of an invariant mean on the weakly almost periodic functions on S or on the almost periodic functions on S. An ergodic theorem of Lloyd [16] is generalized, and a number of examples are presented.     

Generalizations of magic graphs

A graph is magic if the edges are labeled with distinct nonnegative real numbers such that the sum of the labels incident to each vertex is the same. Given a graph finite G, an Abelian group $\text{g}$, and an element r(v) ∈ $\text{g}$ for every v ∈ V(G), necessary and sufficient conditions are given for the existence of edge labels from $\text{g}$ such that the sum of the labels incident to v is r(v). When there do exist labels, all possible labels are determined. The matroid structure of the labels is investigated when $\text{g}$ is an integral domain, and a dimensional structure results. Characterizations of several classes of graphs are given, namely, zero magic, semi-magic, and trivial magic graphs.     

Infinite graphs with the least limiting eigenvalue greater than -2

Let λ(F) be the least eigenvalue of a finite graph F. The least limiting eigenvalue λ(G) of a connected infinite graph G is defined by λ(G)=inf_F{λ(F)}, where F runs over all finite induced subgraphs of G. In [4] and [5] it is proved that λ(G)⩾−2 if and only if G is a generalized line graph. In this paper all connected infinite graphs (thus all generalized line graphs) with λ(G)>−2 are characterized.     

Characterization of self-complementary graphs with 2-factors

Let G be a self-complementary graph (s.c.) and π its degree sequence. Then G has a 2-factor if and only if π - 2 is graphic. This is achieved by obtaining a structure theorem regarding s.c. graphs without a 2-factor. Another interesting corollary of the structure theorem is that if G is a s.c. graph of order p?8 with minimum degree at least $\text{p}\text{4}$, then G has a 2-factor and the result is the best possible.     

Hyperspaces of compact sets in metric linear spaces

We write 2^x for the hyperspace of all non-empty compact sets in a complete metric linear space X topologized by the Hausdorff metric. Using the notation $\text{F}$(X) = {A ϵ 2^X: A is finite}, l^f₂ = {x} = (x_i) ϵ l₂: x_i = 0 for almost all i}, and l^σ₂ = {x = (x _i) ϵ l₂:σ^∞_i=1 (ix_i)² < ∞}, we have the following theorem:A family $\text{G}$ ⊂$\text{F}$(X) is homeomorphic to l^f₂ if $\text{G}$ is σ-fd-compact, the closure $\text{G}$ of $\text{G}$ in 2^x is not locally compact and if whenever A, B ∈ $\text{G}$, λ ∈ [0, 1] and C ⊂ λA + (1 - λ)B with card C⩽ max{card A, card B} then C ϵ $\text{G}$.Moreover, for any G_δ-AR-set $\text{G}$$\text{G}$ of $\text{G}$ with $\text{G}$$\text{G}$ ⊃ $\text{G}$ we have ($\text{G}$$\text{G}$, $\text{G}$)≅(l₂, l^ƒ₂).Similar conditions for hyperspaces to be homeomorphic to l^σ₂ are also established.     

On a generalization of linecritical graphs

Let β(G) be the maximal β such that for any edge xy of G there is an independent β-set that contains no neighbours of x and y. Then $\text{0}\text{}\text{?}\text{β(G)}\text{}\text{?}\text{α(G)?1}$ and G is linecritical iff β(G) = α(G)?1. We determine the minimal connected graphs for any given β(G) or for any given β(G) and α(G). We study the case when β(G)??2 and give upper bounds for the minimal valencies. We generalize some results on linecritical graphs of [1] and [4].