On the commuting probability and supersolvability of finite groups

For a finite group \(G\) , let \(d(G)\) denote the probability that a randomly chosen pair of elements of \(G\) commute. We prove that if \(d(G)>1/s\) for some integer \(s>1\) and \(G\) splits over an abelian normal nontrivial subgroup \(N\) , then \(G\) has a nontrivial conjugacy class inside \(N\) of size at most \(s-1\) . We also extend two results of Barry, MacHale, and Ní Shé on the commuting probability in connection with supersolvability of finite groups. In particular, we prove that if \(d(G)>5/16\) then either \(G\) is supersolvable, or \(G\) isoclinic to \(A_4\) , or \(G/\mathbf{Z}(G)\) is isoclinic to \(A_4\) .     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

Prime graphs of finite groups with a small number of triangles

The prime graph \(\Delta (G)\) of a finite group \(G\) is a graph whose vertices are the primes which divide the degrees of some irreducible complex characters of \(G\) and two distinct primes \(p\) and \(q\) are joined by an edge if the product \(pq\) divides some character degree of \(G\) . In this paper, we determine the upper bounds for the numbers of vertices of the prime graphs of finite groups which possess a small number of triangles. In some cases, we study the structure of such finite groups and their prime graphs in detail.     

On the Chromatic Number of \mathbb {R}^4

The lower bound for the chromatic number of \(\mathbb {R}^4\) is improved from \(7\) to \(9\) . Three graphs with unit distance embeddings in \(\mathbb {R}^4\) are described. The first is a \(7\) -chromatic graph of order \(14\) whose chromatic number can be verified by inspection. The second is an \(8\) -chromatic graph of order \(26\) . In this case the chromatic number can be verified quickly by a simple computer program. The third graph is a \(9\) -chromatic graph of order \(65\) for which computer verification takes about one minute.     

On matching cover of graphs

A k-matching cover of a graph \(G\) is a union of \(k\) matchings of \(G\) which covers \(V(G)\) . The matching cover number of \(G\) , denoted by \(mc(G)\) , is the minimum number \(k\) such that \(G\) has a \(k\) -matching cover. A matching cover of \(G\) is optimal if it consists of \(mc(G)\) matchings of \(G\) . In this paper, we present an algorithm for finding an optimal matching cover of a graph on \(n\) vertices in \(O(n^3)\) time (if use a faster maximum matching algorithm, the time complexity can be reduced to \(O(nm)\) , where \(m=|E(G)|\) ), and give an upper bound on matching cover number of graphs. In particular, for trees, a linear-time algorithm is given, and as a by-product, the matching cover number of trees is determined.     

Isomorphic Steiner symmetrization of p-convex sets

In this paper we show that given a \(p\) -convex set \(K \subset \mathbb{R }^n\) , there exist \(5n\) Steiner symmetrizations that transform it into an isomorphic Euclidean ball. That is, if \(|K| = |D_n| = \kappa _n\) , we may symmetrize it, using \(5n\) Steiner symmetrizations, into a set \(K'\) such that \(c_p D_n \subset K' \subset C_p D_n\) , where \(c_p\) and \(C_p\) are constants dependent on \(p\) only.     

The M-principal graph of a commutative ring

Let \(R\) be a commutative ring and \(M\) be an \(R\) -module. In this paper, we introduce the \(M\) -principal graph of \(R\) , denoted by \(M-PG(R)\) . It is the graph whose vertex set is \(R\backslash \{0\}\) , and two distinct vertices \(x\) and \(y\) are adjacent if and only if \(xM=yM\) . In the special case that \(M=R, M-PG(R)\) is denoted by \(PG(R)\) . The basic properties and possible structures of these two graphs are studied. Also, some relations between \(PG(R)\) and \(M-PG(R)\) are established.     

Mean Squared Error Minimization for Inverse Moment Problems

We consider the problem of approximating the unknown density \(u\in L^2(\Omega ,\lambda )\) of a measure \(\mu \) on \(\Omega \subset \mathbb {R}^n\) , absolutely continuous with respect to some given reference measure \(\lambda \) , only from the knowledge of finitely many moments of \(\mu \) . Given \(d\in \mathbb {N}\) and moments of order \(d\) , we provide a polynomial \(p_d\) which minimizes the mean square error \(\int (u-p)^2d\lambda \) over all polynomials \(p\) of degree at most \(d\) . If there is no additional requirement, \(p_d\) is obtained as solution of a linear system. In addition, if \(p_d\) is expressed in the basis of polynomials that are orthonormal with respect to \(\lambda \) , its vector of coefficients is just the vector of given moments and no computation is needed. Moreover \(p_d\rightarrow u\) in \(L^2(\Omega ,\lambda )\) as \(d\rightarrow \infty \) . In general nonnegativity of \(p_d\) is not guaranteed even though \(u\) is nonnegative. However, with this additional nonnegativity requirement one obtains analogous results but computing \(p_d\ge 0\) that minimizes \(\int (u-p)^2d\lambda \) now requires solving an appropriate semidefinite program. We have tested the approach on some applications arising from the reconstruction of geometrical objects and the approximation of solutions of nonlinear differential equations. In all cases our results are significantly better than those obtained with the maximum entropy technique for estimating \(u\) .     

Low Complexity Methods For Discretizing Manifolds Via Riesz Energy Minimization

Let \(A\) be a compact \(d\) -rectifiable set embedded in Euclidean space \({\mathbb R}^p, d\le p\) . For a given continuous distribution \(\sigma (x)\) with respect to a \(d\) -dimensional Hausdorff measure on \(A\) , our earlier results provided a method for generating \(N\) -point configurations on \(A\) that have an asymptotic distribution \(\sigma (x)\) as \(N\rightarrow \infty \) ; moreover, such configurations are “quasi-uniform” in the sense that the ratio of the covering radius to the separation distance is bounded independently of \(N\) . The method is based upon minimizing the energy of \(N\) particles constrained to \(A\) interacting via a weighted power-law potential \(w(x,y)|x-y|^{-s}\) , where \(s>d\) is a fixed parameter and \(w(x,y)=\left( \sigma (x)\sigma (y)\right) ^{-({s}/{2d})}\) . Here we show that one can generate points on \(A\) with the aforementioned properties keeping in the energy sums only those pairs of points that are located at a distance of at most \(r_N=C_N N^{-1/d}\) from each other, with \(C_N\) being a positive sequence tending to infinity arbitrarily slowly. To do this, we minimize the energy with respect to a varying truncated weight \(v_N(x,y)=\Phi (|x-y|/r_N)\cdot w(x,y)\) , where \(\Phi :(0,\infty )\rightarrow [0,\infty )\) is a bounded function with \(\Phi (t)=0, t\ge 1\) , and \(\lim _{t\rightarrow 0^+}\Phi (t)=1\) . Under appropriate assumptions, this reduces the complexity of generating \(N\) -point “low energy” discretizations to order \(N C_N^d\) computations.     

On an extension of the Frobenius^{\prime } theorem about p-nilpotency of a finite group

Suppose that \(G\) is a finite group and \(H\) is a subgroup of \(G\) . \(H\) is said to be \(s\) -quasinormally embedded in \(G\) if for each prime \(p\) dividing the order of \(H\) , a Sylow \(p\) -subgroup of \(H\) is also a Sylow \(p\) -subgroup of some \(s\) -quasinormal subgroup of \(G\) . We fix in every non-cyclic Sylow subgroup \(P\) of \(G\) some subgroup \(D\) satisfying \(1<|D|<|P|\) and study the \(p\) -nilpotency of \(G\) under the assumption that every subgroup \(H\) of \(P\) with \(|H|=|D|\) is \(s\) -quasinormally embedded in \(G\) . Some recent results and the Frobenius \(^{\prime }\) theorem are generalized.     

A sufficient condition for zero entropy

We prove that a diffeomorphism \(f\) defined on a compact manifold has zero topological entropy if there are \(d\in {\mathbb {N}}\) and \(K>0\) such that \(\Vert Dg^{n_x}(x)\Vert \le Kn^d_x\) for every diffeomorphism \(g\) that is \(C^1\) close to \(f\) and every periodic point \(x\) of least period \(n_x\) of \(g\) .     

Higher derivations and commutativity in lattice-ordered rings

In 1978 I. N. Herstein proved that a prime ring \(R\) of characteristic not two with nonzero derivation \(d\) satisfying \(d(x)d(y)=d(y)d(x)\) for all \(x,y\in R\) is commutative, and in 1995 Bell and Daif showed that \(d(xy)=d(yx)\) implies commutativity. We extend the Bell–Daif theorem to lattice-ordered prime rings with a positive derivation satisfying the property on a one-sided \(L\) -ideal and interpret these conditions for higher derivations in prime \(d\) -rings and in semiprime \(f\) -rings. Our key tool is that every positive derivation nilpotent on a one-sided \(L\) -ideal of a semiprime \(\ell \) -ring is zero on that ideal.     

Endomorphism rings of bimodules

Let \(M\) be an \(R\) - \(R\) -bimodule over a semi-prime right and left Goldie ring \(R\) . We investigate how non-singularity conditions on \(M_R\) are related to such conditions on \(_RM\) . In particular, we say an \(R\) - \(R\) -bimodule \(M\) such that \(_RM\) and \(M_R\) are non-singular has the right essentiality property if \(IM_R\) is essential in \(M_R\) for all essential right ideals \(I\) of \(R\) , and investigate several questions related to this property.     

Maximal Contractive Tuples

Maximality of a contractive tuple of operators is considered. A characterization for a contractive tuple to be maximal is obtained. The notion of maximality for a submodule of the Drury–Arveson module on the \(d\) -dimensional unit ball \({\mathbb {B}}_d\) is defined. For \(d=1\) , it is shown that every submodule of the Hardy module over the unit disc is maximal. But for \(d\ge 2\) we prove that any homogeneous submodule or submodule generated by polynomials is not maximal. A characterization of maximal submodules is obtained.     

On weakly closed subgroups of finite groups

Suppose that \(G\) is a finite group and \(H\) , \(K\) are subgroups of \(G\) . We say that \(H\) is weakly closed in \(K\) with respect to \(G\) if, for any \(g \in G\) such that \(H^{g}\le K\) , we have \(H^{g}=H\) . In particular, when \(H\) is a subgroup of prime-power order and \(K\) is a Sylow subgroup containing it, \(H\) is simply said to be a weakly closed subgroup of \(G\) or weakly closed in \(G\) . In the paper, we investigate the structure of finite groups by means of weakly closed subgroups.     

The Cauchy–Riemann equations in the unit ball of l^{2}

We study the local exactness of the \(\overline{\partial }\) operator in the Hilbert space \(l^2\) for a particular class of \((0,1)\) -forms \(\omega \) of the type \(\omega (z) = \sum _i z_i\omega ^i(z) d\overline{z}_i\) , \(z = (z_i)\) in \(l^2\) . We suppose each function \(\omega ^i\) of class \(C^\infty \) in the closed unit ball of \(l^2\) , of the form \(\omega ^i(z) = \sum _k \omega ^i_k\left( z^k\right) \) , where \(\mathbf N = \bigcup I_k\) is a partition of \(\mathbf N\) , \((\) card \(I_k < +\infty )\) and \(z^k\) is the projection of \(z\) on \(\mathbf C^{I_k}\) . We establish sufficient conditions for exactness of \(\omega \) related to the expansion in Fourier series of the functions \(\omega ^i_k\) .     

On Gromov’s Method of Selecting Heavily Covered Points

A result of Boros and Füredi ( \(d=2\) ) and of Bárány (arbitrary \(d\) ) asserts that for every \(d\) there exists \(c_d>0\) such that for every \(n\) -point set \(P\subset {\mathbb {R}}^d\) , some point of \({\mathbb {R}}^d\) is covered by at least of the \(d\) -simplices spanned by the points of  \(P\) . The largest possible value of \(c_d\) has been the subject of ongoing research. Recently Gromov improved the existing lower bounds considerably by introducing a new, topological proof method. We provide an exposition of the combinatorial component of Gromov’s approach, in terms accessible to combinatorialists and discrete geometers, and we investigate the limits of his method. In particular, we give tighter bounds on the cofilling profiles for the \((n-1)\) -simplex. These bounds yield a minor improvement over Gromov’s lower bounds on \(c_d\) for large \(d\) , but they also show that the room for further improvement through the cofilling profiles alone is quite small. We also prove a slightly better lower bound for \(c_3\) by an approach using an additional structure besides the cofilling profiles. We formulate a combinatorial extremal problem whose solution might perhaps lead to a tight lower bound for  \(c_d\) .     

Formal conserved quantities for isothermic surfaces

Isothermic surfaces in \(S^n\) are characterised by the existence of a pencil \(\nabla ^t\) of flat connections. Such a surface is special of type \(d\) if there is a family \(p(t)\) of \(\nabla ^t\) -parallel sections whose dependence on the spectral parameter \(t\) is polynomial of degree \(d\) . We prove that any isothermic surface admits a family of \(\nabla ^t\) -parallel sections which is a formal Laurent series in \(t\) . As an application, we give conformally invariant conditions for an isothermic surface in \(S^3\) to be special.     

New M-ary sequences with low autocorrelation from interleaved technique

Let \(p\) and \(q\) be two odd primes with \(p=Mf+1\) and \(M\) is even. A new construction of \(M\) -ary sequences of period \(pq\) with low periodic autocorrelation is presented in this paper based on interleaving the \(M\) -ary power residue sequence of period \(p\) according to the quadratic residue with respect to \(q\) . This construction can generate the well-known twin-prime sequence and generalized cyclotomy sequence of order two if \(M=2\) . For \(M=4\) , a new class of quaternary sequences of period \(pq\) with maximal nontrivial autocorrelation value being either \(\sqrt{5}\) or \(3\) is obtained. This achieves the best known results for such kind of quaternary sequences.     

A New Topological Helly Theorem and Some Transversal Results

We prove that for a topological space \(X\) with the property that \( H_{*}(U)=0\) for \(*\ge d\) and every open subset \(U\) of \(X\) , a finite family of open sets in \(X\) has nonempty intersection if for any subfamily of size \(j,\,1\le j\le d+1,\) the \((d-j)\) -dimensional homology group of its intersection is zero. We use this theorem to prove new results concerning transversal affine planes to families of convex sets.