On the homotopy type of CW-complexes with aspherical fundamental group

This paper is concerned with the homotopy type distinction of finite CW-complexes. A (G,n)-complex is a finite n-dimensional CW-complex with fundamental-group G and vanishing higher homotopy-groups up to dimension n−1. In case G is an n-dimensional group there is a unique (up to homotopy) (G,n)-complex on the minimal Euler-characteristic level χmin(G,n). For every n we give examples of n-dimensional groups G for which there exist homotopically distinct (G,n)-complexes on the level χmin(G,n)+1. In the case where n=2 these examples are algebraic.     

Characterization of almost maximally almost-periodic groups

Let G be an Abelian group. We prove that a group G admits a Hausdorff group topology τ such that the von Neumann radical n(G,τ) of (G,τ) is non-trivial and finite iff G has a non-trivial finite subgroup. If G is a topological group, then n(n(G))≠n(G) if and only if n(G) is not dually embedded. In particular, n(n(Z,τ))=n(Z,τ) for any Hausdorff group topology τ on Z.     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

Module homomorphisms and multipliers on locally compact quantum groups

For a Banach algebra A with a bounded approximate identity, we investigate the A-module homomorphisms of certain introverted subspaces of A^∗, and show that all A-module homomorphisms of A^∗ are normal if and only if A is an ideal of A∗∗. We obtain some characterizations of compactness and discreteness for a locally compact quantum group G. Furthermore, in the co-amenable case we prove that the multiplier algebra of L¹(G) can be identified with M(G). As a consequence, we prove that G is compact if and only if LUC(G)=WAP(G) and M(G)≅Z(LUC^∗(G)); which partially answer a problem raised by Volker Runde.     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

Equivariant Nielsen fixed point theory for n-valued maps

We develop an equivariant Nielsen fixed point theory for n-valued G-maps by associating (as in Better (2010) [2]) an abstract simplicial complex to any equivariant n-valued map and defining, in terms of this complex, two n-valued continuous G-homotopy invariants that are lower bounds for the number of fixed points and of orbits in the n-valued continuous G-homotopy class of a given n-valued G-map. We also provide an equivariant Hopf construction for n-valued G-maps as well as a minimality result for the Nielsen numbers introduced in this setting.     

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.     

Equivariant collapses and the homotopy type of iterated clique graphs

The clique graph K(G) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K⁰(G)=G, Kⁿ⁺¹(G)=K(Kⁿ(G)). We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results, it can be easily inferred that Kⁿ(G) is homotopy equivalent to G for every n if G belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper, we show two infinite classes of clique-divergent graphs that satisfy G?Kⁿ(G) for all n, moreover Kⁿ(G) and G are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.     

Identifications in modular group algebras

Let G be a group, S a subgroup of G, and F a field of characteristic p. We denote the augmentation ideal of the group algebra FG by ω(G). The Zassenhaus-Jennings-Lazard series of G is defined by D_n(G)=G∩(1+ωⁿ(G)). We give a constructive proof of a theorem of Quillen stating that the graded algebra associated with FG is isomorphic as an algebra to the enveloping algebra of the restricted Lie algebra associated with the D_n(G). We then extend a theorem of Jennings that provides a basis for the quotient ωⁿ(G)/ωⁿ⁺¹(G) in terms of a basis of the restricted Lie algebra associated with the D_n(G). We shall use these theorems to prove the main results of this paper. For G a finite p-group and n a positive integer, we prove that G∩(1+ω(G)ωⁿ(S))=D_n+1(S) and G∩(1+ω²(G)ωⁿ(S))=D_n+2(S)D_n+1(S∩D₂(G)). The analogous results for integral group rings of free groups have been previously obtained by Gruenberg, Hurley, and Sehgal.     

The existence of even factors in iterated line graphs

An even factor of a graph is a spanning subgraph of G in which all degrees are even, positive integers. In this paper, we characterize the claw-free graphs having even factors and then prove that the n-iterated line graph Lⁿ(G) of G has an even factor if and only if every end branch of G has length at most n and every odd branch-bond of G has a branch of length at most n+1.     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

Isomorphisms,automorphisms, and generalized involution models of projective reflection groups

We investigate the generalized involution models of the projective reflection groups G(r, p, q, n). This family of groups parametrizes all quotients of the complex reflection groups G(r, p, n) by scalar subgroups. Our classification is ultimately incomplete, but we provide several necessary and sufficient conditions for generalized involution models to exist in various cases. In the process we solve several intermediate problems concerning the structure of projective reflection groups. We derive a simple criterion for determining whether two groups G(r, p, q, n) and G(r, p′, q′, n) are isomorphic. We also describe explicitly the form of all automorphisms of G(r, p, q, n), outside a finite list of exceptional cases. Building on prior work, this allows us to prove that G(r, p, 1, n) has a generalized involution model if and only if G(r, p, 1, n) ≌ G(r, 1, p, n). We also classify which groups G(r, p, q, n) have generalized involution models when n = 2, or q is odd, or n is odd.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

Structure of digraphs associated with quadratic congruences with composite moduli

We assign to each positive integer n a digraph G(n) whose set of vertices is H={0,1,…,n-1} and for which there exists a directed edge from a∈H to b∈H if . Associated with G(n) are two disjoint subdigraphs: G₁(n) and G₂(n) whose union is G(n). The vertices of G₁(n) correspond to those residues which are relatively prime to n. The structure of G₁(n) is well understood. In this paper, we investigate in detail the structure of G₂(n).     

On the nullity of tricyclic graphs

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. It is known that η(G)?n-2 if G is a simple graph on n vertices and G is not isomorphic to nK₁. The extremal graphs attaining the upper bound n-2 and the second upper bound n-3 have been obtained. In this paper, the graphs with nullity n-4 are characterized. Furthermore the tricyclic graphs with maximum nullity are discussed.     

Vertex pancyclicity and new sufficient conditions

For a graph G, ??(G) denotes the minimum degree of G. In 1971, Bondy proved that, if G is a 2-connected graph of order n and d(x)?+?d(y)????n for each pair of non-adjacent vertices x,y in G, then G is pancyclic or G?=?K _n/2,n/2. In 2001, Xu proved that, if G is a 2-connected graph of order n????6 and |N(x)????N(y)|?+???(G)????n for each pair of non-adjacent vertices x,y in G, then G is pancyclic or G?=?K _n/2,n/2. In this paper, we introduce a new sufficient condition of generalizing degree sum and neighborhood union and prove that, if G is a 2-connected graph of order n????6 and |N(x)????N(y)|?+?d(w)????n for any three vertices x,y,w of d(x,y)?=?2 and wx or $wy\not\in E(G)$ in G, then G is 4-vertex pancyclic or G belongs to two classes of well-structured exceptional graphs. This result also generalizes the above results.     

Some results on the spectral radii of bicyclic graphs

A bicyclic graph is a connected graph in which the number of edges equals the number of vertices plus one. Let Δ(G) and ρ(G) denote the maximum degree and the spectral radius of a graph G, respectively. Let B(n) be the set of bicyclic graphs on n vertices, and B(n,Δ)={G∈B(n)∣Δ(G)=Δ}. When Δ≥(n+3)/2 we characterize the graph which alone maximizes the spectral radius among all the graphs in B(n,Δ). It is also proved that for two graphs G₁ and G₂ in B(n), if Δ(G₁)>Δ(G₂) and Δ(G₁)≥⌈7n/9⌉+9, then ρ(G₁)>ρ(G₂).     

Permutation polytopes and indecomposable elements in permutation groups

Each group G of n×n permutation matrices has a corresponding permutation polytope, P(G):=conv(G)⊂Rn×n. We relate the structure of P(G) to the transitivity of G. In particular, we show that if G has t nontrivial orbits, then min{2t,⌊n/2⌋} is a sharp upper bound on the diameter of the graph of P(G). We also show that P(G) achieves its maximal dimension of ²(n−1) precisely when G is 2-transitive. We then extend the results of Pak [I. Pak, Four questions on Birkhoff polytope, Ann. Comb. 4 (1) (2000) 83-90] on mixing times for a random walk on P(G). Our work depends on a new result for permutation groups involving writing permutations as products of indecomposable permutations.     

The group marriage problem

Let G be a permutation group acting on [n]={1,…,n} and V={Vi:i=1,…,n} be a system of n subsets of [n]. When is there an element g∈G so that g(i)∈Vi for each i∈[n]? If such a g exists, we say that G has a G-marriage subject to V. An obvious necessary condition is the orbit condition: for any nonempty subset Y of [n], there is an element g∈G such that the image of Y under g is contained in _?y∈YVy. Keevash observed that the orbit condition is sufficient when G is the symmetric group Sn; this is in fact equivalent to the celebrated Hall's Marriage Theorem. We prove that the orbit condition is sufficient if and only if G is a direct product of symmetric groups. We extend the notion of orbit condition to that of k-orbit condition and prove that if G is the cyclic group Cn where n?4 or G acts 2-transitively on [n], then G satisfies the (n−1)-orbit condition subject to V if and only if G has a G-marriage subject to V.