On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

Graphic Sequences with a Realization Containing a Union of Cliques

An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = K_m1∪ K_m2∪...∪ K_mk when n is a sufficiently large integer. This is accomplished by determining σ(K_j + kK₂,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ m_i.     

Erd?s-Ko-Rado theorem for irreducible imprimitive reflection groups

Let Ω be a finite set, and let G be a permutation group on Ω. A subset H of G is called intersecting if for any σ, π ∈ H, they agree on at least one point. We show that a maximal intersecting subset of an irreducible imprimitive reflection group G(m, p, n) is a coset of the stabilizer of a point in {1, …, n} provided n is sufficiently large.     

Schreier type theorems for bicrossed products

We prove that the bicrossed product of two groups is a quotient of the pushout of two semidirect products. A matched pair of groups (H;G; α; β) is deformed using a combinatorial datum (σ; v; r) consisting of an automorphism σ of H, a permutation v of the set G and a transition map r: G → H in order to obtain a new matched pair (H; (G; *); α′, β′) such that there exists a σ-invariant isomorphism of groups H _α⋈β G ≅H _{α′⋈β′} (G, *). Moreover, if we fix the group H and the automorphism σ ∈ Aut H then any σ-invariant isomorphism H _α⋈β G ≅ H _{α′⋈β′} G′ between two arbitrary bicrossed product of groups is obtained in a unique way by the above deformation method. As applications two Schreier type classification theorems for bicrossed products of groups are given.     

On subgroups of the general linear group that contain a maximal nonsplit torus

The paper deals with the structure of intermediate subgroups of the general linear group GL(n, k) of degree n over a field k of odd characteristic that contain a nonsplit maximal torus related to a radical extension of degree n of the ground field k. The structure of ideal nets over a ring that determine the structure of intermediate subgroups containinga transvection is given. Let K = k( ⁿ?{d} ) K = k\left( {\sqrt[n]{d}} \right) be a radical degree-n extension of a field k of odd characteristic, and let T =(d) be a nonsplit maximal torus, which is the image of the multiplicative group of the field K under the regular embedding in G =GL(n, k). In the paper, the structure of intermediate subgroups H, T ≤ H ≤ G, that contain a transvection is studied. The elements of the matrices in the torus T = T (d) generate a subring R(d) in the field k.Let R be an intermediate subring, R(d) ⊆ R ⊆ k, d ∈ R. Let σ_R denote the net in which the ideal dR stands on the principal diagonal and above it and all entries of which beneath the principal diagonal are equal to R. Let σ^R denote the net in which all positions on the principal diagonal and beneath it are occupied by R and all entries above the principal diagonal are equal to dR. Let E(σ_R) be the subgroup generated by all transvections from the net group G(σ_R). In the paper it is proved that the product TE(σ_R) is a group (and thus an intermediate subgroup). If the net σ associated with an intermediate subgroup H coincides with σ_R,then TE(σ_R) ≤ H ≤ N(σ_R),where N(σ_R) is the normalizer of the elementary net group E(σ_R) in G. For the normalizer N(σ_R),the formula N(σ_R)= TG(σ^R) holds. In particular, this result enables one to describe the maximal intermediate subgroups. Bibliography: 13 titles.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

A two-to-one map and abelian affine difference sets

Let D be an affine difference set of order n in an abelian group G relative to a subgroup N. Set = H \ {1, ω}, where H = G/N and . Using D we define a two-to-one map g from to N. The map g satisfies g(σ ^m ) = g(σ) ^m and g(σ) = g(σ ⁻¹) for any multiplier m of D and any element σ ∈ . As applications, we present some results which give a restriction on the possible order n and the group theoretic structure of G/N.      

Normal Hopf subalgebras in cocycle deformations of finite groups

Let G be a finite group and let π : G → G′ be a surjective group homomorphism. Consider the cocycle deformation L = H ^σ of the Hopf algebra H = k ^G of k-valued linear functions on G, with respect to some convolution invertible 2-cocycle σ. The (normal) Hopf subalgebra corresponds to a Hopf subalgebra . Our main result is an explicit necessary and sufficient condition for the normality of L′ in L. This work was partially supported by CONICET, Fundación Antorchas, Agencia Córdoba Ciencia, ANPCyT and Secyt (UNC).     

On the algebraic independence in the selberg class

We prove that a functionF of the Selberg class ℐ is ab-th power in ℐ, i.e.,F=H ^b for someHσ ℐ, if and only ifb divides the order of every zero ofF and of everyp-componentF _p. This implies that the equationF ^a=G^b with (a, b)=1 has the unique solutionF=H ^b andG=H ^a in ℐ. As a consequence, we prove that ifF andG are distinct primitive elements of ℐ, then the transcendence degree of ℂ[F,G] over ℂ is two.     

Planar algebra of the subgroup-subfactor

We give an identification between the planar algebra of the subgroupsubfactor R ⋊ H ⊂ R ⋊ G and the G-invariant planar subalgebra of the planar algebra of the bipartite graph ★ _n , where n = [G: H]. The crucial step in this identification is an exhibition of a model for the basic construction tower, and thereafter of the standard invariant of R ⋊ H ⊂ R ⋊ G in terms of operator matrices. We also obtain an identification between the planar algebra of the fixed algebra subfactor R ^G ⊂ R ^H and the G-invariant planar subalgebra of the planar algebra of the ‘flip’ of ★ _n .     

Degree Sums,Connectivity and Dominating Cycles in Graphs

Let G be a graph of order n with connectivity κ≥3 and let α be the independence number of G. Set σ₄(G)= min{∑⁴ _{i =1} d(x _i ):{x ₁,x ₂,x ₃,x ₄} is an independent set of G}. In this paper, we will prove that if σ₄(G)≥n+2κ, then there exists a longest cycle C of G such that V(G−C) is an independent set of G. Furthermore, if the minimum degree of G is at least α, then G is hamiltonian. Received: July 31, 1998?Final version received: October 4, 2000     

On precover classes

Sunto LetG andH be abstract classes of modules. The classH is said to have theG-property if to each infinite cardinal λ there exists a cardinal κ>λ such that for everyF∈H with |F|≥κ and every its submoduleK with |F/K|≤λ there exists a submoduleL ofK such thatF/L/teG and |F/L|<κ. This condition is stronger than the condition (P) requiringL≠0 instead of |F/L|<κ, which was introduced and investigated in [8]. In this note we are going to study the relations of this more general condition to the existence of precovers with respect to some classes of modules. As an application we obtain some sufficient conditions for the existence of σ-torsionfree precovers related to a given hereditary torsion theory σ for the categoryR-mod. This result is closely related to and in some sense extends that of [5]. The research has been partially supported by the Grant Agency of the Czech Republic, grant #GAČR 201/03/0937 and also by the institutional grant MSM 113 200 007.     

A poisson formula for solvable Lie groups

Given a probability measure μ on a locally compact second countable groupG the space of bounded μ-harmonic functions can be identified withL ^∞(η, α) where (η, α) is a BorelG-space with a σ-finite quasiinvariant measure α. Our goal is to show that when μ is an arbitrary spread out probability measure on a connected solvable Lie groupG then the μ-boundary (η, α) is a contractive homogeneous space ofG. Our approach is based on a study of a class of strongly approximately transitive (SAT) actions ofG. A BorelG-space η with a σ-finite quasiinvariant measure α is called SAT if it admits a probability measurev≪α, such that for every Borel set A with α(A)≠0 and every ε>0 there existsg∈G with ν(gA)>1−ε. Every μ-boundary is a standard SATG-space. We show that for a connected solvable Lie group every standard SATG-space is transitive, characterize subgroupsH⊆G such that the homogeneous spaceG/H is SAT, and establish that the following conditions are equivalent forG/H: (a)G/H is SAT; (b)G/H is contractive; (c)G/H is an equivariant image of a μ-boundary.     

Farrell cohomology and Brown theorems for profinite groups

LetG be a profinite group which has an open subgroupH such that the cohomologicalp-dimensiond≔cd_p(H) is finite (p is a fixed prime). The main result of this paper expresses thep-primary part of high degree cohomology ofG in terms of the elementary abelianp-subgroups ofG: From the latter one constructs a natural profinite simplicial setA G, on whichG acts by conjugation. ThenH ⁿ(G,M)≅H _G ⁿ (AG,M) holds forn≧d+r and everyp-primary discreteG-moduleM (r≔p-rank ofG). If one uses profinite Farrell cohomology, which is introduced in this paper, the analogous fact holds in all degrees. These results are the profinite analogues of theorems by K.S. Brown for discrete groups.     

The fitting length of solvableH pn-groups

For a (finite) groupG and some prime powerp ⁿ, theH _p ⁿ -subgroupH _pn (G) is defined byH _p ⁿ (G)=〈xεG|x ^pn≠1〉. A groupH≠1 is called aH _p ⁿ -group, if there is a finite groupG such thatH is isomorphic toH _p ⁿ (G) andH _p ⁿ (G)≠G. It is known that the Fitting length of a solvableH _p ⁿ -group cannot be arbitrarily large: Hartley and Rae proved in 1973 that it is bounded by some quadratic function ofn. In the following paper, we show that it is even bounded by some linear function ofn. In view of known examples of solvableH _p ⁿ -groups having Fitting lengthn, this result is “almost” best possible.