The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

On Representations of Integers in Thin Subgroups of {{\rm SL}_2({\mathbb {Z}})}

Let ${\Gamma < {\rm SL}(2, {\mathbb Z})}Let G < SL(2, \mathbb Z){\Gamma < {\rm SL}(2, {\mathbb Z})} be a free, finitely generated Fuchsian group of the second kind with no parabolics, and fix two primitive vectors v₀, w₀ ? \mathbb Z²  \  {0}{v_{0}, w_{0} \in \mathbb {Z}^{2} \, {\backslash} \, \{0\}}. We consider the set S{\mathcal {S}} of all integers occurring in áv₀g, w₀?{\langle v_{0}\gamma, w_{0}\rangle}, for g ? G{\gamma \in \Gamma} and the usual inner product on \mathbb R²{\mathbb {R}^2}. Assume that the critical exponent δ of Γ exceeds 0.99995, so that Γ is thin but not too thin. Using a variant of the circle method, new bilinear forms estimates and Gamburd’s 5/6-th spectral gap in infinite-volume, we show that S{\mathcal {S}} contains almost all of its admissible primes, that is, those not excluded by local (congruence) obstructions. Moreover, we show that the exceptional set \mathfrak E(N){\mathfrak {E}(N)} of integers |n| < N which are locally admissible (n ? S   (mod  q)   for all   q 3 1){(n \in \mathcal {S} \, \, ({\rm mod} \, q) \, \, {\rm for\,all} \,\, q \geq 1)} but fail to be globally represented, n ? S{n \notin \mathcal {S}}, has a power savings, |\mathfrak E(N)| << N^1-e₀{|\mathfrak {E}(N)| \ll N^{1-\varepsilon_{0}}} for some ${\varepsilon_{0} > 0}${\varepsilon_{0} > 0}, as N → ∞.     

A Property of Isometric Mappings Between Dual Polar Spaces of Type {DQ (2n, {\mathbb K})}

Let f be an isometric embedding of the dual polar space ${\Delta = DQ(2n, {\mathbb K})}Let f be an isometric embedding of the dual polar space D = DQ(2n, \mathbb K){\Delta = DQ(2n, {\mathbb K})} into D￠ = DQ(2n, \mathbb K￠){\Delta^\prime = DQ(2n, {\mathbb K}^\prime)}. Let P denote the point-set of Δ and let e￠: D￠? S￠ @ PG(2ⁿ - 1, \mathbb K￠){e^\prime : \Delta^\prime \rightarrow {\Sigma^\prime} \cong {\rm PG}(2^n - 1, {{\mathbb K}^\prime})} denote the spin-embedding of Δ′. We show that for every locally singular hyperplane H of Δ, there exists a unique locally singular hyperplane H′ of Δ′ such that f(H) = f(P) ?H￠{f(H) = f(P) \cap H^\prime}. We use this to show that there exists a subgeometry S @ PG(2ⁿ - 1, \mathbb K){\Sigma \cong {\rm PG}(2^n - 1, {\mathbb K})} of Σ′ such that: (i) e￠°f (x) ? S{e^\prime \circ f (x) \in \Sigma} for every point x of D; (ii) e : = e￠°f{\Delta; ({\rm ii})\,e := e^\prime \circ f} defines a full embedding of Δ into Σ, which is isomorphic to the spin-embedding of Δ.     

On r-recognition by prime graph of Bp(3) where p is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G @ B_p(3){G\cong B_p(3)} or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then G @ B₃(3), C₃(3), D₄(3){G\cong B_3(3), C_3(3), D_4(3)}, or G/O₂(G) @ Aut(²B₂(8)){G/O_2(G)\cong {\rm Aut}(^2B_2(8))}. As a corollary, the main result of the above paper is obtained.     

Stability of unitary SK<Subscript>1</Subscript> of Azumaya algebras

For an Azumaya algebra A with center C of rank n ² and a unitary involution τ, we study the stability of the unitary SK₁ under reduction. We show that if R = C ^τ is a Henselian ring with maximal ideal \mathfrakm{\mathfrak{m}} and 2 and n are invertible in R then SK₁(A, t) @ SK₁(A/ \mathfrakm A, overline t){{{\rm SK}_1}(A, \tau) \cong {{\rm SK}_1}(A/ \mathfrak{m} A, overline \tau)}.     

Characterization of $ {\mathbb{A}_{16}} $ by a noncommuting graph

Let G be a finite non-Abelian group. We define a graph Γ _G ; called the noncommuting graph of G; with a vertex set G − Z(G) such that two vertices x and y are adjacent if and only if xy ≠ yx: Abdollahi, Akbari, and Maimani put forward the following conjecture (the AAM conjecture): If S is a finite non-Abelian simple group and G is a group such that Γ _S ≅ Γ _G ; then S ≅ G: It is still unknown if this conjecture holds for all simple finite groups with connected prime graph except \mathbbA₁₀ {\mathbb{A}_{10}} , L ₄(8), L ₄(4), and U ₄(4). In this paper, we prove that if \mathbbA₁₆ {\mathbb{A}_{16}} denotes the alternating group of degree 16; then, for any finite group G; the graph isomorphism G_\mathbbA16 @ G_G {\Gamma_{{\mathbb{A}_{16}}}} \cong {\Gamma_G} implies that \mathbbA₁₆ @ G {\mathbb{A}_{16}} \cong G .     

Some Poincaré-type inequalities for functions of bounded deformation involving the deviatoric part of the symmetric gradient

It is proved that if Ω ⊂ Rⁿ {R^n}  is a bounded Lipschitz domain, then the inequality || u ||₁ \leqslant c(n)\textdiam( W)ò_W | e^D(u) | {\left\| u \right\|_1} \leqslant c(n){\text{diam}}\left( \Omega \right)\int\limits_\Omega {\left| {{\varepsilon^D}(u)} \right|} is valid for functions of bounded deformation vanishing on ∂Ω. Here e^D(u) {\varepsilon^D}(u) denotes the deviatoric part of the symmetric gradient and ò_W | e^D(u) | \int\limits_\Omega {\left| {{\varepsilon^D}(u)} \right|} stands for the total variation of the tensor-valued measure e^D(u) {\varepsilon^D}(u) . Further results concern possible extensions of this Poincaré-type inequality. Bibliography: 27 titles.     

Asymptotic Behavior of Variable-Coefficient Toeplitz Determinants

For a continuous function s\sigma defined on [0,1]×\mathbbT[0,1]\times\mathbb{T}, let \ops\op\sigma stand for the (n+1)×(n+1)(n+1)\times(n+1) matrix whose (j,k)(j,k)-entries are equal to \frac1 2pò₀^2p s( \fracjn,e^iq) e^-i(j-k)q  dq,        j,k = 0,1,...,n . \displaystyle \frac{1} {2\pi}\int_0^{2\pi} \sigma \left( \frac{j}{n},e^{i\theta}\right) e^{-i(j-k)\theta} \,d\theta, \qquad j,k =0,1,\dots,n~. These matrices can be thought of as variable-coefficient Toeplitz matrices or as the discrete analogue of pseudodifferential operators. Under the assumption that the function s\sigma possesses a logarithm which is sufficiently smooth on [0,1]×\mathbbT[0,1]\times\mathbb{T}, we prove that the asymptotics of the determinants of \ops\op\sigma are given by det[\ops] ~ G[s]⁽ⁿ⁺¹⁾E[s]     \text as   n?￥ , \det \left[\op\sigma\right] \sim G[\sigma]^{(n+1)}E[\sigma] \quad \text{ as \ } n\to\infty~, where G[s]G[\sigma] and E[s]E[\sigma] are explicitly determined constants. This formula is a generalization of the Szegö Limit Theorem. In comparison with the classical theory of Toeplitz determinants some new features appear.     

Abelian coverings of finite general linear groups and an application to their non-commuting graphs

In this paper we introduce and study a family A_n(q)\mathcal{A}_{n}(q) of abelian subgroups of GL_n(q){\rm GL}_{n}(q) covering every element of GL_n(q){\rm GL}_{n}(q). We show that A_n(q)\mathcal{A}_{n}(q) contains all the centralizers of cyclic matrices and equality holds if q>n. For q>2, we obtain an infinite product expression for a probabilistic generating function for |A_n(q)||\mathcal{A}_{n}(q)|. This leads to upper and lower bounds which show in particular that

An Inverse Theorem for the Uniformity Seminorms Associated with the Action of {{\mathbb {F}^{\infty}_{p}}}

Let ${\mathbb {F}}Let \mathbb F{\mathbb {F}} a finite field. We show that the universal characteristic factor for the Gowers–Host–Kra uniformity seminorm U ^k (X) for an ergodic action (T_g)_{g ? \mathbb F^w}{(T_{g})_{{g} \in \mathbb {F}^{\omega}}} of the infinite abelian group \mathbb F^w{\mathbb {F}^{\omega}} on a probability space X = (X, B, m){X = (X, \mathcal {B}, \mu)} is generated by phase polynomials f: X ? S¹{\phi : X \to S^{1}} of degree less than C(k) on X, where C(k) depends only on k. In the case where k ￡ char(\mathbb F){k \leq {\rm char}(\mathbb {F})} we obtain the sharp result C(k) = k. This is a finite field counterpart of an analogous result for \mathbb Z{\mathbb {Z}} by Host and Kra [HK]. In a companion paper [TZ] to this paper, we shall combine this result with a correspondence principle to establish the inverse theorem for the Gowers norm in finite fields in the high characteristic case k ￡ char(\mathbb F){k \leq {\rm char}(\mathbb {F})} , with a partial result in low characteristic.     

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

Linear Maps Preserving Operators of Local Spectral Radius Zero

Let X be a complex Banach space and let B(X){\mathcal{B}(X)} be the space of all bounded linear operators on X. For x ? X{x \in X} and T ? B(X){T \in \mathcal{B}(X)}, let r_T(x) = limsup_{n ? ￥} || Tⁿx|| ^1/n{r_{T}(x) =\limsup_{n \rightarrow \infty} \| T^{n}x\| ^{1/n}} denote the local spectral radius of T at x. We prove that if j: B(X) ? B(X){\varphi : \mathcal{B}(X) \rightarrow \mathcal{B}(X)} is linear and surjective such that for every x ? X{x \in X} we have r _T (x) = 0 if and only if r_j(T)(x) = 0{r_{\varphi(T)}(x) = 0}, there exists then a nonzero complex number c such that j(T) = cT{\varphi(T) = cT} for all T ? B(X){T \in \mathcal{B}(X) }. We also prove that if Y is a complex Banach space and j:B(X) ? B(Y){\varphi :\mathcal{B}(X) \rightarrow \mathcal{B}(Y)} is linear and invertible for which there exists B ? B(Y, X){B \in \mathcal{B}(Y, X)} such that for y ? Y{y \in Y} we have r _T (By) = 0 if and only if r_{j( T)} (y)=0{ r_{\varphi ( T) }(y)=0}, then B is invertible and there exists a nonzero complex number c such that j(T) = cB^-1TB{\varphi(T) =cB^{-1}TB} for all T ? B(X){T \in \mathcal{B}(X)}.     

Simple exceptional groups of Lie type are determined by their character degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G)={c(1)  |  c ? Irr(G)}{{\rm cd}(G)=\{\chi(1)\;|\;\chi\in {\rm Irr}(G)\}} be the set of all irreducible complex character degrees of G forgetting multiplicities, and let X₁(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be any non-abelian simple exceptional group of Lie type. In this paper, we will show that if S is a non-abelian simple group and cd(S) í cd(H){{\rm cd}(S)\subseteq {\rm cd}(H)} then S must be isomorphic to H. As a consequence, we show that if G is a finite group with X₁(G) í X₁(H){{\rm X}_1(G)\subseteq {\rm X}_1(H)} then G is isomorphic to H. In particular, this implies that the simple exceptional groups of Lie type are uniquely determined by the structure of their complex group algebras.     

The intersection of subgroups of finite <Emphasis Type="Italic">p</Emphasis>-groups

For a finite p-group G and a positive integer k let I _k (G) denote the intersection of all subgroups of G of order p ^k . This paper classifies the finite p-groups G with I_k(G) @ C_p^k-1{{I}_k(G)\cong C_{p^{k-1}}} for primes p > 2. We also show that for any k, α ≥ 0 with 2(α + 1) ≤ k ≤ n−α the groups G of order p ⁿ with I_k(G) @ C_p^k-a{{I}_k(G)\cong C_{p^{k-\alpha}}} are exactly the groups of exponent p ^n-α .     

A q-analogue of the FKG inequality and some applications

Let L be a finite distributive lattice and μ: L → ℝ⁺ a log-supermodular function. For functions k: L → ℝ⁺ let

On Linear Fractional Transformations Associated with Generalized J-Inner Matrix Functions

A class U_k1 (J){\mathcal{U}}_{\kappa 1} (J) of generalized J-inner mvf’s (matrix valued functions) W(λ) which appear as resolvent matrices for bitangential interpolation problems in the generalized Schur class of p ×q  mvf￠s S_k^{p ×q}p \times q \, {\rm mvf's}\, {\mathcal{S}}_{\kappa}^{p \times q} and some associated reproducing kernel Pontryagin spaces are studied. These spaces are used to describe the range of the linear fractional transformation T_W based on W and applied to S_k2^{p ×q}{\mathcal{S}}_{\kappa 2}^{p \times q}. Factorization formulas for mvf’s W in a subclass U^°_k1 (J) of U_k1(J){\mathcal{U}^{\circ}_{\kappa 1}} (J)\, {\rm of}\, {\mathcal{U}}_{\kappa 1}(J) found and then used to parametrize the set S_k1+k2^{p ×q} ?T_W [ S_k2^{p ×q} ]{\mathcal{S}}_{{\kappa 1}+{\kappa 2}}^{p \times q} \cap T_{W} \left[ {\mathcal{S}}_{\kappa 2}^{p \times q} \right]. Applications to bitangential interpolation problems in the class S_k1+k2^{p ×q}{\mathcal{S}}_{{\kappa 1}+{\kappa 2}}^{p \times q} will be presented elsewhere.     

Bounds on smooth matrix coefficients on L 2-spaces

Let G be a semisimple Lie group with a finite number of connected components and a finite center. Let K be a maximal compact subgroup. Let X be a smooth G-space equipped with a G-invariant measure. In this paper, we give upper bounds for K-finite and ${\mathfrak k}Let G be a semisimple Lie group with a finite number of connected components and a finite center. Let K be a maximal compact subgroup. Let X be a smooth G-space equipped with a G-invariant measure. In this paper, we give upper bounds for K-finite and \mathfrak k{\mathfrak k}-smooth matrix coefficients of the regular representation L ²(X) under an assumption about supp(L²(X)) ?[^(G)]_K{{\rm supp}(L^2(X)) \cap \hat G_K}. Furthermore, we show that this bound holds for unitary representations that are weakly contained in L ²(X). Our result generalizes a result of Cowling–Haagerup–Howe (J Reine Angew Math 387:97–110, 1988). As an example, we discuss the matrix coefficients of the O(p, q) representation L²(\mathbbR^p+q){L^2(\mathbb{R}^{p+q})}.     

An Introduction to Closed/Open Neighborhood Sums: Minimax, Maximin, and Spread

For a graph G of order |V(G)| = n and a real-valued mapping f:V(G)?\mathbbR{f:V(G)\rightarrow\mathbb{R}}, if S ì V(G){S\subset V(G)} then f(S)=?_{w ? S} f(w){f(S)=\sum_{w\in S} f(w)} is called the weight of S under f. The closed (respectively, open) neighborhood sum of f is the maximum weight of a closed (respectively, open) neighborhood under f, that is, NS[f]=max{f(N[v])|v ? V(G)}{NS[f]={\rm max}\{f(N[v])|v \in V(G)\}} and NS(f)=max{f(N(v))|v ? V(G)}{NS(f)={\rm max}\{f(N(v))|v \in V(G)\}}. The closed (respectively, open) lower neighborhood sum of f is the minimum weight of a closed (respectively, open) neighborhood under f, that is, NS^-[f]=min{f(N[v])|v ? V(G)}{NS^{-}[f]={\rm min}\{f(N[v])|v\in V(G)\}} and NS^-(f)=min{f(N(v))|v ? V(G)}{NS^{-}(f)={\rm min}\{f(N(v))|v\in V(G)\}}. For W ì \mathbbR{W\subset \mathbb{R}}, the closed and open neighborhood sum parameters are NS_W[G]=min{NS[f]|f:V(G)? W{NS_W[G]={\rm min}\{NS[f]|f:V(G)\rightarrow W} is a bijection} and NS_W(G)=min{NS(f)|f:V(G)? W{NS_W(G)={\rm min}\{NS(f)|f:V(G)\rightarrow W} is a bijection}. The lower neighbor sum parameters are NS^-_W[G]=maxNS^-[f]|f:V(G)? W{NS^{-}_W[G]={\rm max}NS^{-}[f]|f:V(G)\rightarrow W} is a bijection} and NS^-_W(G)=maxNS^-(f)|f:V(G)? W{NS^{-}_W(G)={\rm max}NS^{-}(f)|f:V(G)\rightarrow W} is a bijection}. For bijections f:V(G)? {1,2,?,n}{f:V(G)\rightarrow \{1,2,\ldots,n\}} we consider the parameters NS[G], NS(G), NS ⁻[G] and NS ⁻(G), as well as two parameters minimizing the maximum difference in neighborhood sums.