Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

Wheel inequalities for stable set polytopes

We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytopeP _G of a graphG. Each “wheel configuration” gives rise to two such inequalities. The simplest wheel configuration is an “odd” subdivisionW of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing forP _W . Generalizations arise by allowing subdivision paths to intersect, and by replacing the “hub” of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time. Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. Research partially supported by scholarships from the Ontario Ministry of Colleges and Universities.     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Preduals of semigroup algebras

For a locally compact group G, the measure convolution algebra M(G) carries a natural coproduct. In previous work, we showed that the canonical predual C ₀(G) of M(G) is the unique predual which makes both the product and the coproduct on M(G) weak^*-continuous. Given a discrete semigroup S, the convolution algebra ℓ ¹(S) also carries a coproduct. In this paper we examine preduals for ℓ ¹(S) making both the product and the coproduct weak^*-continuous. Under certain conditions on S, we show that ℓ ¹(S) has a unique such predual. Such S include the free semigroup on finitely many generators. In general, however, this need not be the case even for quite simple semigroups and we construct uncountably many such preduals on ℓ ¹(S) when S is either ℤ₊×ℤ or (ℕ,⋅).     

A Note on Range-Restricted Circuit Covers

 Let Cone(G), Int.Cone(G) and Lat(G) be the cone, the integer cone and the lattice of the incidence vectors of the circuits of graph G. A good range is a set ?⊆ℕ such that Cone (G)∩Lat (G)∩?^E⊆Int.Cone(G) for every graph G(V,E). We give a counterexample to a conjecture of Goddyn [1] stating that ℕ\{1} is a good range. Received: November 26, 1997     

Steinberg triality groups acting on 2 ? (<Emphasis Type="Italic">v,k</Emphasis>, 1) designs

A 2 - (υ, k, 1) design D = (ℙ,ℙ, ℬ) is a system consisting of a finite set ℙ of υ points and a collection ℬ of ℙ-subsets of ℙ, called blocks, such that each 2-subset of ℙ is contained in precisely one block. Let G be an automorphism group of a 2-(υ, k, 1) design. Delandtsheer proved that if G is block-primitive and D is not a projective plane, then G is almost simple, that is, T ⩽ G ⩽ Aut(T), where T is a non-abelian simple group. In this paper, we prove that T is not isomorphic to ³ D ₄(q). This paper is part of a project to classify groups and designs where the group acts primitively on the blocks of the design.     

Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ². If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000     

On the Exel Crossed Product of Topological Covering Maps

For dynamical systems defined by a covering map of a compact Hausdorff space and the corresponding transfer operator, the associated crossed product C ^*-algebras C(X)⋊ _α,ℒℕ introduced by Exel and Vershik are considered. An important property for homeomorphism dynamical systems is topological freeness. It can be extended in a natural way to in general non-invertible dynamical systems generated by covering maps. In this article, it is shown that the following four properties are equivalent: the dynamical system generated by a covering map is topologically free; the canonical embedding of C(X) into C(X)⋊ _α,ℒℕ is a maximal abelian C ^*-subalgebra of C(X)⋊ _α,ℒℕ; any nontrivial two sided ideal of C(X)⋊ _α,ℒℕ has non-zero intersection with the embedded copy of C(X); a certain natural representation of C(X)⋊ _α,ℒℕ is faithful. This result is a generalization to non-invertible dynamics of the corresponding results for crossed product C ^*-algebras of homeomorphism dynamical systems.     

Lois de sortie et semi-groupes basiques

Let ℙ=(P ^t ) ^t<0 be a semigroup of kernel and letm be an excessive reference measure for ℙ. In this work we prove that ℙ ism-basic if and only if everym.a.e. finite purely excessive function is represented by a unique exit law for ℙ. In this case we deduce some applications about natural densities, energie functionnal and invariant functions for the time-space semigroup of ℙ.      

Aspects of the conjugacy class structure of simple algebraic groups

Let G be an adjoint simple algebraic group over an algebraically closed field of characteristic p; let Φ be the root system of G, and take t∈ℕ. Lawther has proven that the dimension of the set G _[t]={g∈G:g ^t =1} depends only on Φ and t. In particular the value is independent of the characteristic p; this was observed for t small and prime by Liebeck. Since G _[t] is clearly a disjoint union of conjugacy classes the question arises as to whether a similar result holds if we replace G _[t] by one of those classes. This paper provides a partial answer to that question. A special case of what we have proven is the following. Take p,q to be distinct primes and G _p and G _q to be adjoint simple algebraic groups with the same root system and over algebraically closed fields of characteristic p and q respectively. If s∈G _p has order q then there exists an element u∈G _q such that o(u)=o(s) and dimu^G_q=dims^G_p\dim u^{G_{q}}=\dim s^{G_{p}} .     

Logarithm laws for flows on homogeneous spaces

In this paper we generalize and sharpen D. Sullivan’s logarithm law for geodesics by specifying conditions on a sequence of subsets {A _t  | t∈ℕ} of a homogeneous space G/Γ (G a semisimple Lie group, Γ an irreducible lattice) and a sequence of elements f _t of G under which #{t∈ℕ | f _t x∈A _t } is infinite for a.e. x∈G/Γ. The main tool is exponential decay of correlation coefficients of smooth functions on G/Γ. Besides the general (higher rank) version of Sullivan’s result, as a consequence we obtain a new proof of the classical Khinchin-Groshev theorem on simultaneous Diophantine approximation, and settle a conjecture recently made by M. Skriganov. Oblatum 27-VII-1998 & 2-IV-1999 / Published online: 5 August 1999     

On some special measures on βG

LetG be a discrete abelian group,Ĝ the character group ofG, andl ^∞(G)^* the conjugate ofl ^∞(G) equipped with an Arens product. In many cases, we can find unitary functionsf such that χf is almost convergent to zero for all χ∈Ĝ. Some of these functions are then used to produce elements μ∈l ^∞(G)^* such that γμ=0 whenever γ is an annihilator ofC ₀(G). Regarded as Borel measures on βG, these elements satisfyxμ=0 for allx∈βG/G. They belong to the radical ofl ^∞(G)^*, and each of them generates a left ideal ofl ^∞(G)^* that contains no minimal left ideal.     

On the Equicontinuity Region of Discrete Subgroups of <Emphasis Type="Italic">PU</Emphasis>(1,<Emphasis Type="Italic">n</Emphasis>)

Let G be a discrete subgroup of PU(1,n). Then G acts on ℙ_ℂ ⁿ preserving the unit ball ℍ_ℂ ⁿ , where it acts by isometries with respect to the Bergman metric. In this work we look at its action on all of ℙ_ℂ ⁿ and determine its equicontinuity region Eq(G). This turns out to be the complement of the union of all complex projective hyperplanes in ℙ_ℂ ⁿ which are tangent to ∂ℍ_ℂ ⁿ at points in the Chen-Greenberg limit set Λ(G), a closed G-invariant subset of ∂ℍ_ℂ ⁿ which is minimal for non-elementary groups. We also prove that the action on Eq(G) is discontinuous. Also , if the limit set is “sufficiently general” (i.e. it is not contained in any proper k -chain), then each connected component of Eq(G) is a holomorphy domain and it is a complete Kobayashi hyperbolic space.     

The moduli space of (3,3,3) trilinear forms

LetU, V andW be three dimensional vector spaces over ∉ (or an alebraically closed field with characteristic not equal to 2 or 3). We prove that the moduli space of trilinear forms onU ^* ⊗V ^* ⊗W ^* is isomorphic to ℙ² by applying Geometric Invariant Theory to the action ofPGL(U)×PGL(V)×PGL(W) on ℙU⊗V⊗W).     

Difference algebraic subgroups of commutative algebraic groups over finite fields

We study the question of which torsion subgroups of commutative algebraic groups over finite fields are contained in modular difference algebraic groups for some choice of a field automorphism. We show that if G is a simple commutative algebraic group over a finite field of characteristic p, ? is a prime different from p, and for some difference closed field (?, σ) the ?-primary torsion of G(?) is contained in a modular group definable in (?, σ), then it is contained in a group of the form {x∈G(?) :σ(x) =[a](x) } with a∈ℕ\p ^ℕ. We show that no such modular group can be found for many G of interest. In the cases that such equations may be found, we recover an effective version of a theorem of Boxall. Received: 28 May 1998 / Revised version: 20 December 1998     

Contractions of infrainvariant systems of subgroups

We create a method which allows an arbitrary group G with an infrainvariant system ℒ(G) of subgroups to be embedded in a group G* with an infrainvariant system ℒ(G*) of subgroups, so that G _α^* ∩G ∈ ℒ(G) for every subgroup G _α^* ∩G ∈ ℒ(G*) and each factor B/A of a jump of subgroups in ℒ(G*) is isomorphic to a factor of a jump in ℒ(G), or to any specified group H. Using this method, we state new results on right-ordered groups. In particular, it is proved that every Conrad right-ordered group is embedded with preservation of order in a Conrad right-ordered group of Hahn type (i.e., a right-ordered group whose factors of jumps of convex subgroups are order isomorphic to the additive group ℝ); every right-ordered Smirnov group is embedded in a right-ordered Smirnov group of Hahn type; a new proof is given for the Holland–McCleary theorem on embedding every linearly ordered group in a linearly ordered group of Hahn type.     

On the divisor class group of double solids

For a double solid V→ℙ_3> branched over a surface B⊂ℙ₃(ℂ) with only ordinary nodes as singularities, we give a set of generators of the divisor class group in terms of contact surfaces of B with only superisolated singularities in the nodes of B. As an application we give a condition when H ^* (˜V , ℤ) has no 2-torsion. All possible cases are listed if B is a quartic. Furthermore we give a new lower bound for the dimension of the code of B. Received: 16 November 1998     

A problem on semigroups satisfying permutation identities

Let σ be a nontrivial permutation of ordern. A semigroupS is said to be σ-permutable ifx ₁ x ₂ ...x _n =x _σ(1) x _σ(2) ...x _σ(n) , for every (x ₁ ,x ₂,...,x _n )∈S ⁿ . A semigroupS is called(r,t)-commutative, wherer,t are in ℕ^*, ifx ₁ ...x _r x _r+1 ...x _r+t =x _r+1 ...x _r+t x ₁ ...x _r , for every (x ₁ ,x ₂,...,x _r+t ∈S ^r+t . According to a result of M. Putcha and A. Yaqub ([11]), if σ is a fixed-point-free permutation andS is a σ-permutable semigroup then there existsk ∈ ℕ^* such thatS is (1,k)-commutative. In [8], S. Lajos raises up the problem to determine the leastk=k(n) ∈ ℕ^* such that, for every fixed-point-free permutation σ of ordern, every σ-permutable semigroup is also (1,k)-commutative. In this paper this problem is solved for anyn less than or equal to eight and also whenn is any odd integer. For doing this we establish that if a semigroup satisfies a permutation identity of ordern then inevitably it also satisfies some permutation identities of ordern+1.     

Aging in two-dimensional Bouchaud's model

Let E _x be a collection of i.i.d. exponential random variables. Symmetric Bouchaud's model on ℤ² is a Markov chain X(t) whose transition rates are given by w _xy = ν exp (−βE _x ) if x, y are neighbours in ℤ². We study the behaviour of two correlation functions: ℙ[X(t _w +t) = X(t _w )] and ℙ[X(t') = X(t _w ) ∀ t'∈ [t _w , t _w + t]]. We prove the (sub)aging behaviour of these functions when β > 1.