Mathematical programming models for some smallest-world problems

Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs.     

Some inverse problems involving conditional expectations

Let (Ω, F, P) be a probability space, let H be a sub-σ-algebra of F, and let Y be positive and H-measurable with E[Y] = 1. We discuss the structure of the convex set CE(Y; H) = {X ∈ pF: Y = E[X|H]} of random variables whose conditional expectation given H is the prescribed Y. Several characterizations of extreme points of CE(Y; H) are obtained. A necessary and sufficient condition is given in order that CE(Y; H) be the closed, convex hull of its extreme points. For the case of finite F we explicitly calculate the extreme points of CE(Y; H), identify pairs of adjacent extreme points, and characterize extreme points of CE(Y; H) ? CE(Z; G), where G is a second sub-σ-algebra of F and Z ∈ pG. When H = σ(Y) and appropriate topological hypotheses hold, extreme points of CE(Y; H) are shown to be in explicit one-to-one correspondence with certain left inverses of Y. Finally, it is shown how the same approach can be applied to the problem of extremal random measures on $\text{R}$₊ with a prescribed compensator, to deduce that the number of extreme points is zero or one.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

Linear-time computation of optimal subgraphs of decomposable graphs

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well-known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We suggest a general approach for constructing linear-time algorithms in the case where the graph G is defined by certain rules of composition (as are trees, series-parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a property that is “regular” with respect to these rules of composition (as do matchings, dominating sets, and independent sets for all the classes just mentioned). This approach is applied to obtain a linear-time algorithm for computing the irredundance number of a tree, a problem for which no polynomial-time algorithm was previously known.     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

Finding Well-Conditioned Similarities to Block-Diagonalize Nonsymmetric Matrices Is NP-Hard

Given an upper triangular matrix A ∈ R^n×n and a tolerance τ, we show that the problem of finding a similarity transformation G such that G⁻¹AG is block diagonal with the condition number of G being at most τ is NP-hard. Let ƒ(n) be a polynomial in n. We also show that the problem of finding a similarity transformation G such that G⁻¹AG is block-diagonal with the condition number of G being at most ƒ(n) times larger than the smallest possible is NP-hard.     

Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs

We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.     

On the existence of free topological groups

Given a Tychonoff space X and classes U and V of topological groups, we say that a topological group G = G(X, U, V) is a free (U,V)-group over X if (a) X is a subspace of G, (b) G ϵ U, and (c) every continuous f: X → H with H ϵ V extends uniquely to a continuous homomorphism f̄: G→H. For certain classes U and V, we consider the question of the existence of free (U,V)- groups. Our principal results are the following. Let PA and CA denote, respectively, the class ofpseudocompact Abelian groups and the class of compact Abelian groups. Then

• 1.(a) there is a free (PA,PA)-group over X iff; X=Ø and
• 2.(b) there is for each X a free (PA,CA)-group over X in which X is closed.

     

Primitive words,free factors and measure preservation

Let F _k be the free group on k generators. A word w ∈ F _k is called primitive if it belongs to some basis of F _k . We investigate two criteria for primitivity, and consider more generally subgroups of F _k which are free factors. The first criterion is graph-theoretic and uses Stallings core graphs: given subgroups of finite rank H ≤ J ≤ F _k we present a simple procedure to determine whether H is a free factor of J. This yields, in particular, a procedure to determine whether a given element in F _k is primitive. Again let w ∈ F _k and consider the word map w: G × … × G → G (from the direct product of k copies of G to G), where G is an arbitrary finite group. We call w measure preserving if given uniform measure on G × … × G, w induces uniform measure on G (for every finite G). This is the second criterion we investigate: it is not hard to see that primitivity implies measure preservation, and it was conjectured that the two properties are equivalent. Our combinatorial approach to primitivity allows us to make progress on this problem and, in particular, prove the conjecture for k = 2. It was asked whether the primitive elements of F _k form a closed set in the profinite topology of free groups. Our results provide a positive answer for F ₂.     

Modules over group rings of solvable groups with rank restrictions on subgroups

Let A be an R G-module over a commutative ring R, where G is a group of infinite section p-rank (0-rank), C _G (A) = 1, A is not a Noetherian R-module, and the quotient A/C _A (H) is a Noetherian R-module for every proper subgroup H of infinite section p-rank (0-rank). We describe the structure of solvable groups G of this type.     

A finiteness theorem for primal extensions

A set W⊆V(G) is called homogeneous in a graph G if 2?|W|?|V(G)|-1, and N(x)?W=N(y)?W for each x,y∈W. A graph without homogeneous sets is called prime. A graph H is called a (primal) extension of a graph G if G is an induced subgraph of H, and H is a prime graph. An extension H of G is minimal if there are no extensions of G in the set ISub(H)?{H}. We denote by Ext(G) the set of all minimal extensions of a graph G.We investigate the following problem: find conditions under which Ext(G) is a finite set. The main result of Giakoumakis (Discrete Math. 177 (1997) 83-97) is the following sufficient condition.

Theorem. If every homogeneous set of G has exactly two vertices thenExt(G)is a finite set.     

Finite Fourier transform for functions with restricted support

Let G(q) denote the multiplicative group of invertible elements in Z_q, the ring of integers modulo q. Let H be a subgroup of G(q), and let aH be a coset of H in G(q). Suppose ?:Z_q→C is a function with support contained in aH. This paper describes how to find sets K ? Z_q with |K|=|H| such that the function ? can be recovered from the values of its (finite) Fourier transform restricted to K. The proofs involve analyzing the (finite) Fourier transform by means of its associated matrix.     

The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell [5] and Ne?et?il and Rödl [12]. On the other hand, it follows from Alvarez theorem [2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).     

Two, more readily computable, equivariant Nielsen numbers II

In this paper, we present and make computations of two equivariant Nielsen type numbers NG(f(H),k(H)) and NG(f(H),k(H)). The second one is new, while the first one extends and clarifies one given earlier by the author and Jianhan Guo. Both numbers were defined here in terms of Nielsen theory of M-ads introduced in the prequel to this work. The theory of M-ads is also used to give both upper and lower bounds on our numbers, and to make specific computations. Our numbers moreover, fit together in the same way that the two Nielsen type periodic point numbers NPn(f) and NΦn(f) fit together. In particular, we show that NG(f(H),k(H)) is greater than or equal to a sum of numbers of the form NG(f(K),k(K)), and give conditions for equality and Möbius inversion. The periodic point theory results are then seen to follow from what are actually generalizations of them.We work with both fixed point, and coincidence point classes, in the context of a category with essentiality which we introduced in the prequel on M-ads. It is intended that this paper be read in tandem with said prequel.     

Torsion and Abelianization in Equivariant Cohomology

Let X be a topological space upon which a compact connected Lie group G acts. It is well known that the equivariant cohomology H ^* _G (X; Q) is isomorphic to the subalgebra of Weyl group invariants of the equivariant cohomology H ^* _T (X; Q), where T is a maximal torus of G. This relationship breaks down for coefficient rings k other than Q. Instead, we prove that under a mild condition on k the algebra H ^* _G (X; k) is isomorphic to the subalgebra of H ^* _T (X; k) annihilated by the divided difference operators.     

Relative integral bases over a Hilbert class field

Let K be a number field, H its Hilbert class field and L a Galois extension of K containing H. In this paper, we prove that L|H has a relative integral basis (RIB) if the order of G=Gal(L|H) is odd or if the 2-Sylow subgroups of G are not cyclic. If the order of G is even and the 2-Sylow subgroups are cyclic we reduce the problem of the existence of a RIB to a quadratic extension of H.     

The basis number of the n-cube

The basis number of a graph G is defined as the least integer k such that G has a k-fold basis for its cycle space. MacLane (Fund. Math.28 (1937), 22–32) has shown that a graph is planar if and only if its basis number is ≤2. The basis numbers of certain classes of nonplanar graphs have been previously investigated. The basis number of the n-cube for every n is determined in the paper.     

Stability of homogeneous principal bundles with a classical groupas the structure group

Let G be a connected semisimple linear algebraic group defined over an algebraically closed field k and P ⊂ G a parabolic subgroup without any simple factor. Let H be a connected reductive linear algebraic group defined over the field k such that all the simple quotients of H are of classical type. Take any homomorphism π : P → H such that the image of p is not contained in any proper parabolic subgroup of H. Consider the corresponding principal H-bundle E_P(H) = (G × H)/P over G/P. We prove that E_P (H) is strongly stable with respect to any polarization on G/P.     

On permuteral subgroups in finite groups

The permutizer of a subgroup H in a group G is defined as the subgroup generated by all cyclic subgroups of G that permute with H. Call H permuteral in G if the permutizer of H in G coincides with G; H is called strongly permuteral in G if the permutizer of H in U coincides with U for every subgroup U of G containing H. We study the finite groups with given systems of permuteral and strongly permuteral subgroups and find some new characterizations of w-supersoluble and supersoluble groups.     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.