On the full automorphism group of a graph

While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary we find that, whenG is ap-group with no homomorphism ontoZ _p wrZ _p , almost all Cayley graphs ofG have automorphism group isomorphic toG.     

The Menger property for infinite ordered sets

It is shown that, if an ordered set P contains at most k pairwise disjoint maximal chains, where k is finite, then every finite family of maximal chains in P has a cutset of size at most k. As a corollary of this, we obtain the following Menger-type result that, if in addition, P contains k pairwise disjoint complete maximal chains, then the whole family, M (P), of maximal chains in P has a cutset of size k. We also give a direct proof of this result. We give an example of an ordered set P in which every maximal chain is complete, P does not contain infinitely many pairwise disjoint maximal chains (but arbitrarily large finite families of pairwise disjoint maximal chains), and yet M (P) does not have a cutset of size <x, where x is any given (infinite) cardinal. This shows that the finiteness of k in the above corollary is essential and disproves a conjecture of Zaguia.     

On Residual Nilpotence of Projective Crossed Modules

Abstract

Let F be a free group, (M,?, F) a non-aspherical projective F-crossed module. We prove that the action of Coker (?) on Ker (?) is faithful. Also we show that if (M,?, F) is a residually nilpotent crossed module, then Coker (?) is a residually nilpotent group. As a corollary, we get an alternative proof of Conduche's translation of Whitehead's asphericity conjecture in terms of residual nilpotence of certain crossed modules.     

Weighted scattering matrices of regular coverings of graphs

We give a decomposition formula for the determinant det(I ? U(λ)) of the weighted bond scattering matrix U(λ) of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express some determinant of the weighted bond scattering matrix of a regular covering of G by means of its L-functions.     

On the Kernel of Restriction of Characters*

Let G be a finite group, H be a proper subgroup of G, and S be a unitary subring of C. The kernel of the restriction map S[Irr(G)] → S[Irr(H)] as a ring homomorphism is studied. As a corollary, the main result in [Isaacs, I. M. and Navarro, G., Injective restriction of characters, Arch. Math., 108, 2017, 437–439] is reproved.     

Oriented matroids and Ky Fan’s theorem

L. Lovász (Matroids and Sperner’s Lemma, Europ. J. Comb. 1 (1980), 65–66) has shown that Sperner’s combinatorial lemma admits a generalization involving a matroid defined on the set of vertices of the associated triangulation. We prove that Ky Fan’s theorem admits an oriented matroid generalization of similar nature. Classical Ky Fan’s theorem is obtained as a corollary if the underlying oriented matroid is chosen to be the alternating matroid C ^m,r .     

Centralisers in Surface Braid Groups

Abstract

Let Σ be an orientable surface. We generalise Fenn–Rolfsen–Zhu's results on centralisers of singular braids on the disk to singular braids on Σ. As a corollary, we derive a simple and geometric proof of the fact that the word problem is solvable in the monoid of singular braids on n strands on Σ.     

Remarks on Type III Unprojection

In this note we deal with rational curves in ? ³ which are images of a line by means of a finite sequence of cubo-cubic Cremona transformations. We prove that these curves can always be obtained applying to the line a sequence of such transformations increasing at each step the degree of the curve. As a corollary we get a result about curves that can give speciality for linear systems of ? ³.     

Recognizing String Graphs Is Decidable

Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

On solvability of systems of polynomial equations

We study the computational complexity of the solvability problem of systems of polynomial equations over finite algebras. We prove a new dichotomy theorem that extends most of the dichotomy results which have been obtained over different families of finite algebras so far. As a corollary, for example, we get that if \mathbbA{\mathbb{A}} is a finite algebra of finite signature and omits the Hobby-McKenzie type 1, then the problem is solvable in polynomial time whenever \mathbbA{\mathbb{A}} is a reduct of a generalized affine algebra, and NP-complete otherwise.     

Recognizing String Graphs Is Decidable

   Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

Topological Model Categories Generated by Finite Complexes

 Our main result states that for each finite complex L the category TOP of topological spaces possesses a model category structure (in the sense of Quillen) whose weak equivalences are precisely maps which induce isomorphisms of all [L]-homotopy groups. The concept of [L]-homotopy has earlier been introduced by the first author and is based on Dranishnikov’s notion of extension dimension. As a corollary we obtain an algebraic characterization of [L]-homotopy equivalences between [L]-complexes. This result extends two classical theorems of J. H. C. Whitehead. One of them – describing homotopy equivalences between CW-complexes as maps inducing isomorphisms of all homotopy groups – is obtained by letting L = {point}. The other – describing n-homotopy equivalences between at most (n+1)-dimensional CW-complexes as maps inducing isomorphisms of k-dimensional homotopy groups with k ⩽ n – by letting L = S ⁿ⁺¹ , n ⩾ 0.     

Affine Groups with Two Self-Paired Orbitals

Abstract

In this paper we describe all known instances of primitive soluble groups of affine type which have a single self-paired nondiagonal orbital. We show how to construct representations of the point stabiliser that are imprimitive, semilinear, subfield, or tensor decomposable. As a corollary we give a constructive proof that there exist groups with arbitrarily large numbers of orbitals, only two of which are self-paired.     

The domestic levels ofK c are iterable

We show that the models produced by theK ^c construction before (if ever) it reaches a non-domestic premouse are all iterable. As a corollary we get thatPFA plus the existence of a measurable cardinal implies the existence of a non-domestic premouse. Partially supported by the Italian MURST. Research partially supported by NSF grant DMS 98-03292. Research partially supported by NSF grant DMS 98-03611.     

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary

Abstract. We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in R ⁿ to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit' is a generalization of Rado's theorem on the existence of a linearly independent transversal.     

Variations on polynomial subgroup growth

A groupG hasweak polynomial subgroup growth (wPSG) of degree ≤α if each finite quotient Ḡ ofG contains at most │Ḡ│ ^a subgroups. The main result is that wPSG of degree α implies polynomial subgroup growth (PSG) of degree at mostf(α). It follows that wPSG is equivalent to PSG. A corollary is that if, in a profinite groupG, thek-generator subgroups have positive “density” δ, thenG is finitely generated (the number of generators being bounded by a function ofk and δ).     

Topological Model Categories Generated by Finite Complexes

 Our main result states that for each finite complex L the category TOP of topological spaces possesses a model category structure (in the sense of Quillen) whose weak equivalences are precisely maps which induce isomorphisms of all [L]-homotopy groups. The concept of [L]-homotopy has earlier been introduced by the first author and is based on Dranishnikov’s notion of extension dimension. As a corollary we obtain an algebraic characterization of [L]-homotopy equivalences between [L]-complexes. This result extends two classical theorems of J. H. C. Whitehead. One of them – describing homotopy equivalences between CW-complexes as maps inducing isomorphisms of all homotopy groups – is obtained by letting L = {point}. The other – describing n-homotopy equivalences between at most (n+1)-dimensional CW-complexes as maps inducing isomorphisms of k-dimensional homotopy groups with k ⩽ n – by letting L = S ⁿ⁺¹ , n ⩾ 0. The first author was partially supported by NSERC research grant. Received December 12, 2001; in revised form September 7, 2002 Published online February 28, 2003     

Finite p-Groups All of Whose Proper Quotient Groups are Abelian or Inner-Abelian

In this article, finite p-groups all of whose proper quotient groups are abelian or inner-abelian are classified. As a corollary, finite p-group all of whose proper quotient groups are abelian, and finite p-groups all of whose proper sections are abelian or inner-abelian are also classified.     

Minimal 2-Fold Coverings of E d

Let N(k, d) be the smallest positive integer such that given any finite collection of open halfspaces which k-fold coversE ^d , there exists a subcollection of cardinality less than or equal toN(k,d) which k-fold coversE ^d . A well-known corollary to Helly's theorem proves N(1,d) =d+1. This provides an inductive base from which we show N(k; d) exists for all positive integers k.Our main result is .     

Joint Hyponormality of Rational Toeplitz Pairs

We characterize hyponormal “rational” Toeplitz pairs which are pairs of Toeplitz operators whose symbols are rational functions in L^∞. The main result of this article is as follows. If T = (T_ϕ, T_ψ) is a hyponormal rational Toeplitz pair then ϕ − βψ ∈H² for some constant β; in other words, their co-analytic parts necessarily coincide up to a constant multiple. As a corollary we get a complete characterization of hyponormal rational Toeplitz pairs.