Note on coloring of double disk graphs

The coloring of disk graphs is motivated by the frequency assignment problem. In 1998, Malesińska et al. introduced double disk graphs as their generalization. They showed that the chromatic number of a double disk graph \(G\) is at most \(33\,\omega (G) - 35\) , where \(\omega (G)\) denotes the size of a maximum clique in \(G\) . Du et al. improved the upper bound to \(31\,\omega (G) - 1\) . In this paper we decrease the bound substantially; namely we show that the chromatic number of \(G\) is at most \(15\,\omega (G) - 14\) .     

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.     

Semiclassical limits of ground state solutions to Schrödinger systems

This paper is concerned with the existence and concentration properties of the ground state solutions to the following coupled Schrödinger systems $$\begin{aligned} \left\{ \begin{array}{l} -\varepsilon ^2\varDelta u+u+V(x)v=W(x)G_{v}(z)~\hbox { in }\ {\mathbb {R}}^N,\\ -\varepsilon ^2\varDelta v+v+V(x)u=W(x)G_{u}(z)~\hbox {in } \ {\mathbb {R}}^N,\\ u(x)\rightarrow 0\ \hbox {and }v(x)\rightarrow 0\ \hbox {as } \ |x|\rightarrow \infty , \end{array} \right. \end{aligned}$$ and $$\begin{aligned} \left\{ \begin{array}{l} -\varepsilon ^2\varDelta u+u+V(x)v=W(x)(G_{v}(z)+|z|^{2^*-2}v)~\hbox {in } \ {\mathbb {R}}^N,\\ -\varepsilon ^2\varDelta v+v+V(x)u=W(x)(G_{u}(z)+|z|^{2^*-2}u)~\hbox {in } \ {\mathbb {R}}^N,\\ u(x)\rightarrow 0\ \hbox {and }v(x)\rightarrow 0\ \hbox {as } \ |x|\rightarrow \infty , \end{array} \right. \end{aligned}$$ where \(z=(u,v)\in {\mathbb {R}}^2\) , \(G\) is a power type nonlinearity, having superquadratic growth at both \(0\) and infinity but subcritical, \(V\) can be sign-changing and \(\inf W>0\) . We prove the existence, exponential decay, \(H^2\) -convergence and concentration phenomena of the ground state solutions for small \(\varepsilon >0\) .     

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.     

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\) .     

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).     

Uniqueness of generalized p-area minimizers and integrability of a horizontal normal in the Heisenberg group

We study the uniqueness of generalized \(p\) -minimal surfaces in the Heisenberg group. The generalized \(p\) -area of a graph defined by \(u\) reads \(\int |\nabla u+\vec {F}|+Hu.\) If \(u\) and \(v\) are two minimizers for the generalized \(p\) -area satisfying the same Dirichlet boundary condition, then we can only get \(N_{\vec {F}}(u) = N_{\vec {F}}(v)\) (on the nonsingular set) where \(N_{\vec {F}}(w) := \frac{\nabla w+\vec {F}}{|\nabla w+\vec {F}|}.\) To conclude \(u = v\) (or \(\nabla u = \nabla v)\) , it is not straightforward as in the Riemannian case, but requires some special argument in general. In this paper, we prove that \(N_{\vec {F}}(u) = N_{ \vec {F}}(v)\) implies \(\nabla u = \nabla v\) in dimension \(\ge \) 3 under some rank condition on derivatives of \(\vec {F}\) or the nonintegrability condition of contact form associated to \(u\) or \(v\) . Note that in dimension 2 ( \(n=1),\) the above statement is no longer true. Inspired by an equation for the horizontal normal \(N_{\vec {F}}(u),\) we study the integrability for a unit vector to be the horizontal normal of a graph. We find a Codazzi-like equation together with this equation to form an integrability condition.     

Proper circulant weighing matrices of weight p^2

A circulant weighing matrix \(CW(v,n)\) is a circulant matrix \(M\) of order \(v\) with \(0,\pm 1\) entries such that \(MM^T=nI_v\) . In this paper, we study proper circulant matrices with \(n=p^2\) where \(p\) is an odd prime divisor of \(v\) . For \(p\ge 5\) , it turns out that to search for such circulant matrices leads us to two group ring equations and by studying these two equations, we manage to prove that no proper \(CW(pw,p^2)\) exists when \(p\equiv 3\pmod {4}\) or \(p=5\) .     

On conditional permutability and factorized groups

Two subgroups \(A\) and \(B\) of a group \(G\) are said to be totally completely conditionally permutable (tcc-permutable) if \(X\) permutes with \(Y^g\) for some \(g\in \langle X,Y\rangle \) , for all \(X \le A\) and all \(Y\le B\) . In this paper, we study finite products of tcc-permutable subgroups, focussing mainly on structural properties of such products. As an application, new achievements in the context of formation theory are obtained.     

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.     

Covering of subspaces by subspaces

Lower and upper bounds on the size of a covering of subspaces in the Grassmann graph \(\mathcal{G }_q(n,r)\) by subspaces from the Grassmann graph \(\mathcal{G }_q(n,k)\) , \(k \ge r\) , are discussed. The problem is of interest from four points of view: coding theory, combinatorial designs, \(q\) -analogs, and projective geometry. In particular we examine coverings based on lifted maximum rank distance codes, combined with spreads and a recursive construction. New constructions are given for \(q=2\) with \(r=2\) or \(r=3\) . We discuss the density for some of these coverings. Tables for the best known coverings, for \(q=2\) and \(5 \le n \le 10\) , are presented. We present some questions concerning possible constructions of new coverings of smaller size.     

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.     

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.     

Uncertainty principles and sum complexes

Let \(p\) be a prime and let \(A\) be a nonempty subset of the cyclic group \(C_p\) . For a field \({\mathbb F}\) and an element \(f\) in the group algebra \({\mathbb F}[C_p]\) let \(T_f\) be the endomorphism of \({\mathbb F}[C_p]\) given by \(T_f(g)=fg\) . The uncertainty number \(u_{{\mathbb F}}(A)\) is the minimal rank of \(T_f\) over all nonzero \(f \in {\mathbb F}[C_p]\) such that \(\mathrm{supp}(f) \subset A\) . The following topological characterization of uncertainty numbers is established. For \(1 \le k \le p\) define the sum complex \(X_{A,k}\) as the \((k-1)\) -dimensional complex on the vertex set \(C_p\) with a full \((k-2)\) -skeleton whose \((k-1)\) -faces are all \(\sigma \subset C_p\) such that \(|\sigma |=k\) and \(\prod _{x \in \sigma }x \in A\) . It is shown that if \({\mathbb F}\) is algebraically closed then $$\begin{aligned} u_{{\mathbb F}}(A)=p-\max \{k :\tilde{H}_{k-1}(X_{A,k};{\mathbb F}) \ne 0\}. \end{aligned}$$ The main ingredient in the proof is the determination of the homology groups of \(X_{A,k}\) with field coefficients. In particular it is shown that if \(|A| \le k\) then \(\tilde{H}_{k-1}(X_{A,k};{\mathbb F}_p)\!=\!0.\)      

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.     

Stationary and invariant densities and disintegration kernels

Let \(G\) be a locally compact topological group, acting measurably on some Borel spaces \(S\) and \(T\) , and consider some jointly stationary random measures \(\xi \) on \(S\times T\) and \(\eta \) on \(S\) such that \(\xi (\cdot \times T)\ll \eta \) a.s. Then there exists a stationary random kernel \(\zeta \) from \(S\) to \(T\) such that \(\xi =\eta \otimes \zeta \) a.s. This follows from the existence of an invariant kernel \(\varphi \) from \(S\times {\mathcal {M}}_{S\times T}\times {\mathcal {M}}_S\) to \(T\) such that \(\mu =\nu \otimes \varphi (\cdot ,\mu ,\nu )\) whenever \(\mu (\cdot \times T)\ll \nu \) . Also included are some related results on stationary integration, absolute continuity, and ergodic decomposition.     

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.     

Counting and Sampling Minimum Cuts in Genus g Graphs

Let \(G\) be a directed graph with \(n\) vertices embedded on an orientable surface of genus \(g\) with two designated vertices \(s\) and \(t\) . We show that computing the number of minimum \((s,t)\) -cuts in \(G\) is fixed-parameter tractable in \(g\) . Specifically, we give a \(2^{O(g)} n^2\) time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are no prior results that are fixed-parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample an \((s,t)\) -minimum cut uniformly at random in \(O(n \log n)\) time per sample.     

Optimal mass transport and symmetric representations of their cost functions

We consider Monge–Kantorovich problems corresponding to general cost functions \(c(x,y)\) but with symmetry constraints on a Polish space \(X\times X\) . Such couplings naturally generate anti-symmetric Hamiltonians on \(X\times X\) that are \(c\) -convex with respect to one of the variables. In particular, if \(c\) is differentiable with respect to the first variable on an open subset \(X\) in \( \mathbb {R}^d\) , we show that for every probability measure \(\mu \) on \(X\) , there exists a symmetric probability measure \(\pi _0\) on \(X\times X\) with marginals \(\mu \) , and an anti-symmetric Hamiltonian \(H\) such that \(\nabla _2H(y, x)=\nabla _1c(x,y)\) for \( \pi _0\) -almost all \((x,y) \in X \times X.\) If \(\pi _0\) is supported on a graph \((x, Sx)\) , then \(S\) is necessarily a \(\mu \) -measure preserving involution (i.e., \(S^2=I\) ) and \(\nabla _2H(x, Sx)=\nabla _1c(Sx,x)\) for \(\mu \) -almost all \(x \in X.\) For monotone cost functions such as those given by \(c(x,y)=\langle x, u(y)\rangle \) or \(c(x,y)=-|x-u(y)|^2\) where \(u\) is a monotone operator, \(S\) is necessarily the identity yielding a classical result by Krause, namely that \(u(x)=\nabla _2H(x, x)\) where \(H\) is anti-symmetric and concave-convex.