Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Radical Classes of Lattice-Ordered Groups vs. Classes of Compact Spaces

For a given class T of compact Hausdorff spaces, let Y(T) denote the class of -groups G such that for each gG, the Yosida space Y(g) of g belongs to T. Conversely, if R is a class of ;-groups, then T(R) stands for the class of all spaces which are homeomorphic to a Y(g) for some gGR. The correspondences TY(T) and RT(R) are examined with regard to several closure properties of classes. Several sections are devoted to radical classes of -groups whose Yosida spaces are zero-dimensional. There is a thorough discussion of hyper-projectable -groups, followed by presentations on Y(e.d.), where e.d. denotes the class of compact extremally disconnected spaces, and, for each regular uncountable cardinal , the class Y(disc), where disc stands for the class of all compact -disconnected spaces. Sample results follow. Every strongly projectable -group lies in Y(e.d.). The -group G lies in Y(e.d.) if and only if for each gG Y(g) is zero-dimensional and the Boolean algebra of components of g, comp(g), is complete. Corresponding results hold for Y(disc). Finally, there is a discussion of Y(F), with F standing for the class of compact F-spaces. It is shown that an Archimedean -group G is in Y(F) if and only if, for each pair of disjoint countably generated polars P and Q, G=P +Q .     

Surfaces and the second homology of a group

LetG be a group andK(G, 1) an Eilenberg—MacLane space, i.e. ₁(K(G,1))G, _i (K(G,1))=0,i1. We give a purely algebraic proof that the second homology groupH ₂(G)=H ₂(G,)H ₂(K(G,1)) is isomorphic to the group of stable equivalence classes of continuous mapsFK(G,1) inducing surjections on fundamental groups (resp. surjections, whereF{F _g=closed orientable surface of genusg,g}. As a corollary we obtain an algebraic proof of the well-known isomorphismH ₂(G)₂(K(G,1)) (2-dimensional bordism group).     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Superrigidity of lattices in solvable Lie groups

Summary Let be a closed, cocompact subgroup of a simply connected, solvable Lie groupG, such that Ad _G has the same Zariski closure as AdG. If : GL _n () is any finite-dimensional representation of , we show that virtually extends to a representation ofG. (By combining this with work of Margulis on lattices in semisimple groups, we obtain a similar result for lattices in many groups that are neither solvable nor semisimple.) Furthermore, we show that if is isomorphic to a closed, cocompact subgroup of another simply connected, solvable Lie groupG, then any isomorphism from to extends to a crossed isomorphism fromG toG. In the same vein, we prove a more concrete form of Mostow's theorem that compact solvmanifolds with isomorphic fundamental groups are diffeomorphic.Oblatum 5-VII-1994 & 15-IV-1995     

The Spectral Theory of Amenable Actions and Invariants of Discrete Groups

Let G denote a semisimple group, a discrete subgroup, B=G/P the Poisson boundary. Regarding invariants of discrete subgroups we prove, in particular, the following:(1) For any -quasi-invariant measure on B, and any probablity measure on , the norm of the operator () on L ²(B,) is equal to (), where is the unitary representation in L ²(X,), and is the regular representation of .(2) In particular this estimate holds when is Lebesgue measure on B, a Patterson–Sullivan measure, or a -stationary measure, and implies explicit lower bounds for the displacement and Margulis number of (w.r.t. a finite generating set), the dimension of the conformal density, the -entropy of the measure, and Lyapunov exponents of .(3) In particular, when G=PSL₂() and is free, the new lower bound of the displacement is somewhat smaller than the Culler–Shalen bound (which requires an additional assumption) and is greater than the standard ball-packing bound.We also prove that ()=_G() for any amenable action of G and L ¹(G), and conversely, give a spectral criterion for amenability of an action of G under certain natural dynamical conditions. In addition, we establish a uniform lower bound for the -entropy of any measure quasi-invariant under the action of a group with property T, and use this fact to construct an interesting class of actions of such groups, related to 'virtual' maximal parabolic subgroups. Most of the results hold in fact in greater generality, and apply for instance when G is any semi-simple algebraic group, or when is any word-hyperbolic group, acting on their Poisson boundary, for example.     

Characterization,structure and analysis on abelian ℒ∞ groups

An abelian topological group is an group if and only if it is a locally -compactk-space and every compact subset in it is contained in a compactly generated locally compact subgroup. Every abelian groupG is topologically isomorphic to G ₀ where ₀ andG ₀ is an abelian group where every compact subset is contained in a compact subgroup. Intrinsic definitions of measures, convolution of measures, measure algebra,L ₁-algebra, Fourier transforms of abelian groups are given and their properties are studied.     

Packing circuits in eulerian digraphs

LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK ₆ by –Y andY– operations.     

Circular Chromatic Number and Mycielski Graphs

As a natural generalization of graph coloring, Vince introduced the star chromatic number of a graph G and denoted it by ^*(G). Later, Zhu called it circular chromatic number and denoted it by _c(G). Let (G) be the chromatic number of G. In this paper, it is shown that if the complement of G is non-hamiltonian, then _c(G)=(G). Denote by M(G) the Mycielski graph of G. Recursively define M^m(G)=M(M^m–1(G)). It was conjectured that if mn–2, then _c(M^m(K_n))=(M^m(K_n)). Suppose that G is a graph on n vertices. We prove that if , then _c(M(G))=(M(G)). Let S be the set of vertices of degree n–1 in G. It is proved that if |S| 3, then _c(M(G))=(M(G)), and if |S| 5, then _c(M²(G))=(M²(G)), which implies the known results of Chang, Huang, and Zhu that if n3, _c(M(K_n))=(M(K_n)), and if n5, then _c(M²(K_n))=(M²(K_n)).* Research supported by Grants from National Science Foundation of China and Chinese Academy of Sciences.     

Une méthode de comparaison isopérimétrique de fonctionnelles de domaines de la physique mathématique I. Première partie: une démonstration de la conjecture isopérimétrique Pλ2 ≥ πj 0 4 /2 de Pólya et Szegö

Résumé Soient _G la première valeur propre de la membrane à contour fixé sur un domaine simplement connexeG, etP _G la rigidité à la torsion deG. En construisant un cercleK tel queP _K P _G et _{K G}, on démontre la conjecture de Pólya et Szegö [14]; P_{G G} ² j ₀ ² /2. Ce résultat renforce le théorème isopérimétrique classique de Rayleigh [15], Faber [4] et Krahn [10].

---

Summary Let _G be the first eigenvalue of the fixed membrane on a simply connected domainG, and letP _G be the torsional rigidity ofG. We prove Pólya-Szegö's conjecture [14]: P_{G G} ² j ₀ ² /2, by constructing a circleK such thatP _K P _G and _{K G}. This result sharpens the classical isoperimetric theorem of Rayleigh [15], Faber [4] and Krahn [10].

     

The Topology of the Coloring Complex

In a recent paper, E. Steingrímsson associated to each simple graph G a simplicial complex _G, referred to as the coloring complex of G. Certain nonfaces of _G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial _G of G, and the reduced Euler characteristic is, up to sign, equal to |_G(–1)|–1. We show that _G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of _G, and their Euler characteristics coincide with _G(0) and –_G(1), respectively. We show for a large class of graphs—including all connected graphs—that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.Research financed by ECs IHRP Programme, within the Research Training Network Algebraic Combinatorics in Europe, grant HPRN-CT-2001-00272.     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

Simple modules over the multiparameter quantum function algebra at roots of 1

We construct essentially all the irreducible modules for the multiparameter quantum function algebraF [G], whereG is a simple simply connected complex algebraic group, and is a root of unity.     

Une variante à la Coxeter du groupe de Steinberg

LetG _n ()be the semi-direct product of the symmetric groupS _n by the Steinberg groupSt _n ()of a ringWe first prove thatG _n ()has a Coxeter-type presentation. The canonical morphism St _n () GL _n ()extends to a group homo G_n() GL _n ()We next determine the kernel of for n = We also give an expression for the generator of the algebraic K group K ₂(Z)of the integers in terms of permutation matrices.     

Covering properties and Følner conditions for locally compact groups

Summary LetG be a locally compact group with left Haar measurem _G on the Borel sets IB(G) (generated by open subsets) and write |E|=m _G (E). Consider the following geometric conditions on the groupG.(FC If >0 and compact setKG are given, there is a compact setU with 0<|U|< and |x U U|/|U|< for allxK.(A) If >0 and compact setKG, which includes the unit, are given there is a compact setU with 0<|U|< and |K U U|/|U|<.HereA B=(A/B)(B/A) is the symmetric difference set; by regularity ofm _G it makes no difference if we allowU to be a Borel set. It is well known that (A)(FC) and it is known that validity of these conditions is intimately connected with amenability ofG: the existence of a left invariant mean on the spaceCB(G) of all continuous bounded functions. We show, for arbitrary locally compact groupsG, that (amenable)(FC)(A). The proof uses a covering property which may be of interest by itself: we show that every locally compact groupG satisfies.(C) For at least one setK, with int(K)Ø and compact, there is an indexed family {x J}G such that {Kx } is a covering forG whose covering index at each pointg (the number of J withgKx ) is uniformly bounded throughoutG.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

Isolated points in duals of certain locally compact groups

Summary LetG be a separable locally compact group with dual space. consists of all equivalence classes of irreducible unitary representations ofG, and is endowed with the Fell-topology. We study the topological properties in of the square-integrable representations ofG. [ is square-integrable provided there is a coordinate functiong((g)v, v),gG, for which is inL ²(G) w.r.t. left Haar measure onG.]SupposeG contains an open normal subgroupN of the formeKN ⁿ e whereK is compact. (All groups with a compact invariant neighborhood of the identity, [IN] groups, satisfy this condition.) In this case we show that if is square-integrable then {} is an open point of.Finally, our techniques are used to prove this result for arbitrary (non connected) nilpotent Lie groups.     

Asymptotic Density and the Asymptotics of Partition Functions

Let A be a set of positive integers with gcd (A) = 1, and let p _A (n) be the partition function of A. Let c ₀ = 2/3. If A has lower asymptotic density and upper asymptotic density , then lim inf log p _A (n)/c ₀ n and lim sup log p _A (n)/c ₀ n . In particular, if A has asymptotic density > 0, then log p _A (n) c₀n. Conversely, if > 0 and log p _A (n) c ₀ n, then the set A has asymptotic density .