Branchings in rooted graphs and the diameter of greedoids

LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr ²–r+1 (r>0). This answers a question by L. Lovász.There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr.Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2^r–1.     

The vertex-cover polynomial of a graph

In this paper we define the vertex-cover polynomial Ψ(G,τ) for a graph G. The coefficient of τ^r in this polynomial is the number of vertex covers V′ of G with |V′|=r. We develop a method to calculate Ψ(G,τ). Motivated by a problem in biological systematics, we also consider the mappings f from {1, 2,…,m} into the vertex set V(G) of a graph G, subject to f⁻¹(x)f⁻¹(y)≠ for every edge xy in G. Let F(G,m) be the number of such mappings f. We show that F(G,m) can be determined from Ψ(G,τ).     

On zero-sum -flows of graphs

For a graph G, a zero-sum flow is an assignment of non-zero real numbers on the edges of G such that the total sum of all edges incident with any vertex of G is zero. A zero-sum k-flow for a graph G is a zero-sum flow with labels from the set {±1,…,±(k-1)}. In this paper for a graph G, a necessary and sufficient condition for the existence of zero-sum flow is given. We conjecture that if G is a graph with a zero-sum flow, then G has a zero-sum 6-flow. It is shown that the conjecture is true for 2-edge connected bipartite graphs, and every r-regular graph with r even, r>2, or r=3.     

On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian

The utility of Fiedler vectors in interrogating the structure of graphs has generated intense interest and motivated the pursuit of further theoretical results. This paper focuses on how the Fiedler vectors of one graph reveal structure in a second graph that is related to the first. Specifically, we consider a point of articulation r in the graph G whose Laplacian matrix is L and derive a related graph G_{r} whose Laplacian is the matrix obtained by taking the Schur complement with respect to r in L. We show how Fiedler vectors of G_{r} relate to the structure of G and we provide bounds for the algebraic connectivity of G_{r} in terms of the connected components at r in G. In the case where G is a tree with points of articulation rR, we further consider the graph G_R derived from G by taking the Schur complement with respect to R in L. We show that Fiedler vectors of G_R valuate the pendent vertices of G in a manner consistent with the structure of the tree.     

A note on 1-factors in graphs

Conditions on a graphG are presented which are sufficient to guarantee thatG–Z contains a 1-factor, whereZ is a set of edges ofG of restricted cardinality. These conditions provide generalizations of several known results and, further, establish the result that ifG is anr-regular, (r–2)-edge-connected graph (r2) of even order andz is an integer with 0zr–1 such thatG contains fewer thanr–z edge cut sets of cardinalityr–2, thenG–Z has a 1-factor for each setZ ofz edges ofG.     

The trivial intersection problem for characters of principal indecomposable modules

For a prime p and a finite group G let Φ_p(G) denote the complex character associated to the projective indecomposable module in characteristic p with trivial head. Let Irr(Φ_p(G)) denote the set of irreducible characters occurring as constituents in Φ_p(G). We characterize all finite simple groups which satisfy Irr(Φ_p(G))∩Irr(Φ_q(G))={1_G} for all primes p≠q.     

Strong bias of group generators: an obstacle to the “product replacement algorithm”

Let G be a finite group. Efficient generation of nearly uniformly distributed random elements in G, starting from a given set of generators of G, is a central problem in computational group theory. In this paper we demonstrate a weakness in the popular “product replacement algorithm,” widely used for this purpose. The main results are the following. Let be the set of generating k-tuples of elements of G. Consider the distribution of the first components of the k-tuples in induced by the uniform distribution over  . We show that there exist infinite sequences of groups G such that this distribution is very far from uniform in two different senses: (1) its variation distance from uniform is >1−ε; and (2) there exists a short word (of length (loglog|G|)^O(k)) which separates the two distributions with probability 1−ε. The class of groups we analyze is direct powers of alternating groups. The methods used include statistical analysis of permutation groups, the theory of random walks, the AKS sorting network, and a randomized simulation of monotone Boolean operations by group operations, inspired by Barrington's work on bounded-width branching programs. The problem is motivated by the product replacement algorithm which was introduced in [Comm. Algebra 23 (1995) 4931–4948] and is widely used. Our results show that for certain groups the probability distribution obtained by the product replacement algorithm has a bias which can be detected by a short straight line program.     

Coding into Ramsey sets

In [6] W. T. Gowers formulated and proved a Ramsey-type result which lies at the heart of his famous dichotomy for Banach spaces. He defines the notion of weakly Ramsey set of block sequences of an infinite dimensional Banach space and shows that every analytic set of block sequences is weakly Ramsey. We show here that Gowers’ result follows quite directly from the fact that all G_δ sets are weakly Ramsey, if the Banach space does not contain c₀, and from the fact that all F_σδ sets are weakly Ramsey, in the case of an arbitrary Banach space. We also show that every result obtained by the application of Gowers’ theorem to an analytic set can also be obtained by applying the Theorem to a F_σδ set (or to a G_δ set if the space does not contain c₀). This fact explains why the only known applications of this technique are based on very low-ranked Borel sets (open, closed, F_σ, or G_δ).     

An inverse theorem for the restricted set addition in Abelian groups

Let A be a set of k5 elements of an Abelian group G in which the order of the smallest nonzero subgroup is larger than 2k−3. Then the number of different elements of G that can be written in the form a+a^′, where a,a^′A, a≠a^′, is at least 2k−3, as it has been shown in [Gy. Károlyi, The Erdős–Heilbronn problem in Abelian groups, Israel J. Math. 139 (2004) 349–359]. Here we prove that the bound is attained if and only if the elements of A form an arithmetic progression in G, thus completing the solution of a problem of Erdős and Heilbronn. The proof is based on the so-called ‘Combinatorial Nullstellensatz.’     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

Hamilton Decomposable Graphs with Specified Leaves

In this paper, a simple proof is given of a result that provides necessary and sufficient conditions for the existence of a hamilton decomposition of G–E(H) for any non-bipartite r-regular complete multipartite graph G and for any 2-factor H of G. Such conditions were originally obtained by Buchanan for complete graphs (ie when r=|V(G)|–1), and in some cases by Leach and Rodger otherwise (Leach and Rodger also settled the bipartite case). This result is extended to consider hamilton decompositions of G–E(HF), where F is a 1-factor of G.     

Fast conformal mapping of multiply connected regions

An iterative method is presented which constructs for an unbounded region G with m holes and sufficiently smooth boundary a circular region H and a conformal mapping Φ from H to G. With the usual normalization both H and Φ are uniquely determined by G. With a few modifications the method can also be applied to a bounded region G with m holes. The canonical region H is then the unit disc with m circular holes. The proposed method also determines the centers and radii of the boundary circles of H and requires, at each iterative step, the solution of a Riemann–Hilbert (RH) problem, which has a unique solution. Numerically, the RH problem can be treated efficiently by the method of successive conjugation using the fast Fourier transform (FFT). The iteration for the solution of the RH problem converges linearly. The conformal mapping method converges quadratically. The results of some test calculations exemplify the performance of the method.     

A generalization of Burnside's combinatorial lemma

Let G be a finite group which acts on a set S. We present a method of computing the entire distribution of G-orbits of S (the number of k-element G-orbits of S for all k) in terms of the number of s ε S fixed by every σ ε H for subgroups H of G, and the Möbius function μ(·, ·) defined on the subgroup lattice of G. We deduce Burnside's lemma as a consequence of our result.     

G-pre-invex functions in mathematical programming

In the present paper, we introduce the concept of G-pre-invex functions with respect to η defined on an invex set with respect to η. These function unify the concepts of nondifferentiable convexity, pre-invexity and r-pre-invexity. Furthermore, relationships of G-pre-invex functions to various introduced earlier pre-invexity concepts are also discussed. Some (geometric) properties of this class of functions are also derived. Finally, optimality results are established for optimization problems under appropriate G-pre-invexity conditions.     

Augmenting forests to meet odd diameter requirements

Given a graph G=(V,E) and an integer D≥1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P=NP. For a forest G and an odd D≥3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D; our algorithm delivers an 8-approximate solution in O(|V|³) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected.     

Small subsets of groups

Given an infinite group G and an infinite cardinal κ|G|, we say that a subset A of G is κ-large (κ-small) if there exists F[G]^<κ such that G=FA (GFA is κ-large for each F[G]^<κ). The subject of the paper is the family of all κ-small subsets. We describe the left ideal of the right topological semigroup βG determined by . We study interrelations between κ-small and other (P_κ-small and κ-thin) subsets of groups, and prove that G can be generated by some 2-thin subsets. We partition G in countable many subsets which are κ-small for each κω. We show that [G]^<κ is dual to provided that either κ is regular and κ=|G|, or G is Abelian and κ is a limit cardinal, or G is a divisible Abelian group.     

Analytic continuation of local representations of symmetric spaces

We prove the following analytic continuation theorem which applies to any virtual representation of any symmetric space (G, K, σ). The problem of passing from the Euclidean group to the Poincaré group appears first to have been addressed and solved this way by Klein and Landau. Let G be a Lie group, K a closed subgroup, and σ an involutive automorphism with K as fixed-point subgroup. If = + is the corresponding symmetric Lie algebra, we form ^* = + , and let G^* denote the simply connected Lie group with ^* as Lie algebra. We consider virtual representations π of G on a fixed complex Hilbert space , adopting the definitions due to J. Fröhlich, K. Osterwalder, and E. Seiler; in particular, π(g⁻¹) π(σ(g))^* (possibly unbounded operators) for g in a neighborhood of e in G. We prove that every such π continues analytically to a strongly continuous unitary representation of G^* on . Our theorem extends results due to Klein-Landau, Fröhlich et al., and others, earlier, for special cases. Previous results were known only for special (G, K, σ), and then only for certain π.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

The Ramsey property for graphs with forbidden complete subgraphs

The following theorem is proved: Let G be a finite graph with cl(G) = m, where cl(G) is the maximum size of a clique in G. Then for any integer r ≥ 1, there is a finite graph H, also with cl(H) = m, such that if the edges of H are r-colored in any way, then H contains an induced subgraph G′ isomorphic to G with all its edges the same color.