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.     

Recognition of \text {PSL}(2,p) by order and some information on its character degrees where p is a prime

Let \(G\) be a finite group and \(\text {cd}(G)\) be the set of irreducible character degrees of \(G\) . In this paper we prove that if \(p\) is a prime number, then the simple group \(\text {PSL}(2,p)\) is uniquely determined by its order and some information about its character degrees. In fact we prove that if \(G\) is a finite group such that (i) \(|G|=|\text {PSL}(2,p)|\) , (ii) \(p\in \text {cd}(G)\) , (iii) \(\text {cd}(G)\) has an even integer, and (iv) there does not exist any element \(a\in \text {cd}(G)\) such that \(2p\mid a\) , then \(G\cong \text {PSL}(2,p)\) . As a consequence of our result we get that \(\text {PSL}(2,p)\) is uniquely determined by its order and the largest and the second largest character degrees.     

Bounding the exponent of a verbal subgroup

We deal with the following conjecture. If \(w\) is a group word and \(G\) is a finite group in which any nilpotent subgroup generated by \(w\) -values has exponent dividing \(e\) , then the exponent of the verbal subgroup \(w(G)\) is bounded in terms of \(e\) and \(w\) only. We show that this is true in the case where \(w\) is either the \(n\text{ th }\) Engel word or the word \([x^n,y_1,y_2,\ldots ,y_k]\) (Theorem A). Further, we show that for any positive integer \(e\) there exists a number \(k=k(e)\) such that if \(w\) is a word and \(G\) is a finite group in which any nilpotent subgroup generated by products of \(k\) values of the word \(w\) has exponent dividing \(e\) , then the exponent of the verbal subgroup \(w(G)\) is bounded in terms of \(e\) and \(w\) only (Theorem B).     

A groupoid generalisation of Leavitt path algebras

Let \(G\) be a locally compact, Hausdorff, étale groupoid whose unit space is totally disconnected. We show that the collection \(A(G)\) of locally-constant, compactly supported complex-valued functions on \(G\) is a dense \(*\) -subalgebra of \(C_c(G)\) and that it is universal for algebraic representations of the collection of compact open bisections of \(G\) . We also show that if \(G\) is the groupoid associated to a row-finite graph or \(k\) -graph with no sources, then \(A(G)\) is isomorphic to the associated Leavitt path algebra or Kumjian–Pask algebra. We prove versions of the Cuntz–Krieger and graded uniqueness theorems for \(A(G)\) .     

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.     

Characterization of ellipses as uniformly dense sets with respect to a family of convex bodies

Let \(K\subset \mathbb R ^N\) be a convex body containing the origin. A measurable set \(G\subset \mathbb R ^N\) with positive Lebesgue measure is said to be uniformly \(K\) -dense if, for any fixed \(r>0\) , the measure of \(G\cap (x+r K)\) is constant when \(x\) varies on the boundary of \(G\) (here, \(x+r K\) denotes a translation of a dilation of \(K\) ). We first prove that \(G\) must always be strictly convex and at least \(C^{1,1}\) -regular; also, if \(K\) is centrally symmetric, \(K\) must be strictly convex, \(C^{1,1}\) -regular and such that \(K=G-G\) up to homotheties; this implies in turn that \(G\) must be \(C^{2,1}\) -regular. Then for \(N=2\) , we prove that \(G\) is uniformly \(K\) -dense if and only if \(K\) and \(G\) are homothetic to the same ellipse. This result was already proven by Amar et al. in 2008 . However, our proof removes their regularity assumptions on \(K\) and \(G\) , and more importantly, it is susceptible to be generalized to higher dimension since, by the use of Minkowski’s inequality and an affine inequality, avoids the delicate computations of the higher-order terms in the Taylor expansion near \(r=0\) for the measure of \(G\cap (x+r\,K)\) (needed in 2008).     

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.     

Approximation faible et principe de Hasse pour des espaces homogènes à stabilisateur fini résoluble

Let \(K\) be a global field and \(G\) a finite solvable \(K\) -group. Under certain hypotheses concerning the extension splitting \(G\) , we show that the homogeneous space \(V=G'/G\) with \(G'\) a semi-simple simply connected \(K\) -group has the weak approximation property. We use a more precise version of this result to prove the Hasse principle for homogeneous spaces \(X\) under a semi-simple simply connected \(K\) -group \(G'\) with finite solvable geometric stabilizer \({\bar{G}}\) , under certain hypotheses concerning the \(K\) -kernel (or \(K\) -lien) \(({\bar{G}},\kappa )\) defined by \(X\) .     

Scattered linear sets generated by collineations between pencils of lines

Let \(A\) and \(B\) be two points of \(\mathrm{{PG}}(2,q^n)\) , and let \(\Phi \) be a collineation between the pencils of lines with vertices \(A\) and \(B\) . In this paper, we prove that the set of points of intersection of corresponding lines under \(\Phi \) is either the union of a scattered \(\mathrm{{GF}}(q)\) -linear set of rank \(n+1\) with the line \(AB\) or the union of \(q-1\) scattered \(\mathrm{{GF}}(q)\) -linear sets of rank \(n\) with \(A\) and \(B\) . We also determine the intersection configurations of two scattered \(\mathrm{{GF}}(q)\) -linear sets of rank \(n+1\) of \(\mathrm{{PG}}(2,q^n)\) both meeting the line \(AB\) in a \(\mathrm{{GF}}(q)\) -linear set of pseudoregulus type with transversal points \(A\) and \(B\) .     

Neighbour-transitive codes in Johnson graphs

The Johnson graph \(J(v,k)\) has, as vertices, the \(k\) -subsets of a \(v\) -set \(\mathcal {V}\) and as edges the pairs of \(k\) -subsets with intersection of size \(k-1\) . We introduce the notion of a neighbour-transitive code in \(J(v,k)\) . This is a proper vertex subset \(\Gamma \) such that the subgroup \(G\) of graph automorphisms leaving \(\Gamma \) invariant is transitive on both the set \(\Gamma \) of ‘codewords’ and also the set of ‘neighbours’ of \(\Gamma \) , which are the non-codewords joined by an edge to some codeword. We classify all examples where the group \(G\) is a subgroup of the symmetric group \(\mathrm{Sym}\,(\mathcal {V})\) and is intransitive or imprimitive on the underlying \(v\) -set \(\mathcal {V}\) . In the remaining case where \(G\le \mathrm{Sym}\,(\mathcal {V})\) and \(G\) is primitive on \(\mathcal {V}\) , we prove that, provided distinct codewords are at distance at least \(3\) , then \(G\) is \(2\) -transitive on \(\mathcal {V}\) . We examine many of the infinite families of finite \(2\) -transitive permutation groups and construct surprisingly rich families of examples of neighbour-transitive codes. A major unresolved case remains.     

Empirical likelihood bivariate nonparametric maximum likelihood estimator with right censored data

This article considers the estimation for bivariate distribution function (d.f.) \(F_0(t, z)\) of survival time \(T\) and covariate variable \(Z\) based on bivariate data where \(T\) is subject to right censoring. We derive the empirical likelihood-based bivariate nonparametric maximum likelihood estimator \(\hat{F}_n(t,z)\) for \(F_0(t,z)\) , which has an explicit expression and is unique in the sense of empirical likelihood. Other nice features of \(\hat{F}_n(t,z)\) include that it has only nonnegative probability masses, thus it is monotone in bivariate sense. We show that under \(\hat{F}_n(t,z)\) , the conditional d.f. of \(T\) given \(Z\) is of the same form as the Kaplan–Meier estimator for the univariate case, and that the marginal d.f. \(\hat{F}_n(\infty ,z)\) coincides with the empirical d.f. of the covariate sample. We also show that when there is no censoring, \(\hat{F}_n(t,z)\) coincides with the bivariate empirical d.f. For discrete covariate \(Z\) , the strong consistency and weak convergence of \(\hat{F}_n(t,z)\) are established. Some simulation results are presented.     

Fully inert subgroups of free Abelian groups

A subgroup \(H\) of an Abelian group \(G\) is called fully inert if \((\phi H + H)/H\) is finite for every \(\phi \in \mathrm{End}(G)\) . Fully inert subgroups of free Abelian groups are characterized. It is proved that \(H\) is fully inert in the free group \(G\) if and only if it is commensurable with \(n G\) for some \(n \ge 0\) , that is, \((H + nG)/H\) and \((H + nG)/nG\) are both finite. From this fact we derive a more structural characterization of fully inert subgroups \(H\) of free groups \(G\) , in terms of the Ulm–Kaplansky invariants of \(G/H\) and the Hill–Megibben invariants of the exact sequence \(0 \rightarrow H \rightarrow G \rightarrow G/H \rightarrow 0\) .     

Construction of relative difference sets and Hadamard groups

‘There exist normal \((2m,2,2m,m)\) relative difference sets and thus Hadamard groups of order \(4m\) for all \(m\) of the form $$\begin{aligned} m= x2^{a+t+u+w+\delta -\epsilon +1}6^b 9^c 10^d 22^e 26^f \prod _{i=1}^s p_i^{4a_i} \prod _{i=1}^t q_i^2 \prod _{i=1}^u \left( (r_i+1)/2)r_i^{v_i}\right) \prod _{i=1}^w s_i \end{aligned}$$ under the following conditions: \(a,b,c,d,e,f,s,t,u,w\) are nonnegative integers, \(a_1,\ldots ,a_r\) and \(v_1,\ldots ,v_u\) are positive integers, \(p_1,\ldots ,p_s\) are odd primes, \(q_1,\ldots ,q_t\) and \(r_1,\ldots ,r_u\) are prime powers with \(q_i\equiv 1\ (\mathrm{mod}\ 4)\) and \(r_i\equiv 1\ (\mathrm{mod}\ 4)\) for all \(i, s_1,\ldots ,s_w\) are integers with \(1\le s_i \le 33\) or \(s_i\in \{39,43\}\) for all \(i, x\) is a positive integer such that \(2x-1\) or \(4x-1\) is a prime power. Moreover, \(\delta =1\) if \(x>1\) and \(c+s>0, \delta =0\) otherwise, \(\epsilon =1\) if \(x=1, c+s=0\) , and \(t+u+w>0, \epsilon =0\) otherwise. We also obtain some necessary conditions for the existence of \((2m,2,2m,m)\) relative difference sets in partial semidirect products of \(\mathbb{Z }_4\) with abelian groups, and provide a table cases for which \(m\le 100\) and the existence of such relative difference sets is open.     

Additive mappings satisfying algebraic conditions in rings

Let \(R\) be any \((n+1)!\) -torsion free ring and \(F,D: R\rightarrow R\) be additive mappings satisfying \(F(x^{n+1})=(\alpha (x))^nF(x)+\sum \nolimits _{i=1}^n (\alpha (x))^{n-i}(\beta (x))^iD(x)\) for all \(x\in R\) , where \(n\) is a fixed integer and \(\alpha \) , \(\beta \) are automorphisms of \(R\) . Then, \(D\) is Jordan left \((\alpha , \beta )\) -derivation and \(F\) is generalized Jordan left \((\alpha , \beta )\) -derivation on \(R\) and if additive mappings \(F\) and \(D\) satisfying \(F(x^{n+1})=F(x)(\alpha (x))^n+\sum \nolimits _{i=1}^n (\beta (x))^iD(x)(\alpha (x))^{n-i}\) for all \(x\in R\) . Then, \(D\) is Jordan \((\alpha , \beta )\) -derivation and \(F\) is generalized Jordan \((\alpha , \beta )\) -derivation on \(R\) . At last some immediate consequences of the above theorems have been given.     

Combinatorial solutions providing improved security for the generalized Russian cards problem

We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of \(n\) cards, each given \(a\) , \(b\) , and \(c\) cards, respectively. The goal is for Alice and Bob to learn each other’s hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice’s cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice’s hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of \(t-(n, a, 1)\) -designs, where \(t=a-c\) . We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying \(c = a-d\) for some \(d \ge 2\) , where \(b \ge d-1\) and the strategy is assumed to satisfy a strong version of security (namely perfect \((d-1)\) -security), we show that \(a = d+1\) and hence \(c=1\) . We also give a precise characterization of informative and perfectly \((d-1)\) -secure deals of the form \((d+1, b, 1)\) satisfying \(b \ge d-1\) involving \(d-(n, d+1, 1)\) -designs.     

Growth in solvable subgroups of {{\mathrm{GL}}}_r({\mathbb {Z}}/p{\mathbb {Z}})

Let \(K={\mathbb {Z}}/p{\mathbb {Z}}\) and let \(A\) be a subset of \({{\mathrm{GL}}}_r(K)\) such that \(\langle A \rangle \) is solvable. We reduce the study of the growth of \(A\) under the group operation to the nilpotent setting. Fix a positive number \(C\ge 1\) ; we prove that either \(A\) grows (meaning \(|A_3|\ge C|A|\) ), or else there are groups \(U_R\) and \(S\) , with \(U_R\unlhd S \unlhd \langle A\rangle \) , such that \(S/U_R\) is nilpotent, \(A_k\cap S\) is large and \(U_R\subseteq A_k\) , where \(k\) depends only on the rank \(r\) of \({{\mathrm{GL}}}_r(K)\) . Here \(A_k = \{x_1 x_2 \cdots x_k : x_i \in A \cup A^{-1} \cup \{1\}\}\) . When combined with recent work by Pyber and Szabó, the main result of this paper implies that it is possible to draw the same conclusions without supposing that \(\langle A \rangle \) is solvable.     

On Sub-determinants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron \(P = \{x {\in } {\mathbb {R}}^n :Ax\le b\}\) , where \(A \in {\mathbb {Z}}^{m\times n}\) . The bound is polynomial in \(n\) and the largest absolute value of a sub-determinant of \(A\) , denoted by \(\Delta \) . More precisely, we show that the diameter of \(P\) is bounded by \(O(\Delta ^2 n^4\log n\Delta )\) . If \(P\) is bounded, then we show that the diameter of \(P\) is at most \(O(\Delta ^2 n^{3.5}\log n\Delta )\) . For the special case in which \(A\) is a totally unimodular matrix, the bounds are \(O(n^4\log n)\) and \(O(n^{3.5}\log n)\) respectively. This improves over the previous best bound of \(O(m^{16}n^3(\log mn)^3)\) due to Dyer and Frieze (Math Program 64:1–16, 1994).     

Hyperreflexivity of bounded N-cocycle spaces of banach algebras

Let \(X\) and \(Y\) be Banach spaces, \(n\in \mathbb {N}\) , and \(B^n(X,Y)\) the space of bounded \(n\) -linear maps from \(X\times \ldots \times X\) ( \(n\) -times) into \(Y\) . The concept of hyperreflexivity has already been defined for subspaces of \(B(X,Y)\) , where \(X\) and \(Y\) are Banach spaces. We extend this concept to the subspaces of \(B^n(X,Y)\) , taking into account its \(n\) -linear structure. We then investigate when \(\mathcal {Z}^n(A,X)\) , the space of all bounded \(n\) -cocycles from a Banach algebra \(A\) into a Banach \(A\) -bimodule \(X\) , is hyperreflexive. Our approach is based on defining two notions related to a Banach algebra, namely the strong property \((\mathbb {B})\) and bounded local units, and then applying them to find uniform criterions under which \(\mathcal {Z}^n(A,X)\) is hyperreflexive. We also demonstrate that these criterions are satisfied in variety of examples including large classes of C \(^*\) -algebras and group algebras and thereby providing various examples of hyperreflexive \(n\) -cocyle spaces. One advantage of our approach is that not only we obtain the hyperreflexivity for bounded \(n\) -cocycle spaces in different cases but also our results generalize the earlier ones on the hyperreflexivity of bounded derivation spaces, i.e. when \(n=1\) , in the literature. Finally, we investigate the hereditary properties of the strong property \((\mathbb {B})\) and b.l.u. This allows us to come with more examples of bounded \(n\) -cocycle spaces which are hyperreflexive.     

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.