Vertex transitive graphs from injective linear mappings

Based on a motivation coming from the study of the metric structure of the category of finite dimensional vector spaces over a finite field \(\mathbb {F}\) , we examine a family of graphs, defined for each pair of integers \(1 \le k \le n\) , with vertex set formed by all injective linear transformations \(\mathbb {F}^k \rightarrow \mathbb {F}^n\) and edges corresponding to pairs of mappings, \(f\) and \(g\) , with \(\lambda (f,g)= \dim \mathrm{Im }(f-g)=1 \) . For \(\mathbb {F}\cong \mathrm{GF }(q)\) , this graph will be denoted by \(\mathrm{INJ }_q(k,n)\) . We show that all such graphs are vertex transitive and Hamiltonian and describe the full automorphism group of each \(\mathrm{INJ }_q (k,n)\) for \(k . Using the properties of line-transitive groups, we completely determine which of the graphs \(\mathrm{INJ }_q (k,n)\) are Cayley and which are not. The Cayley ones consist of three infinite families, corresponding to pairs \((1,n),\,(n-1,n)\) , and \((n,n)\) , with \(n\) and \(q\) arbitrary, and of two sporadic examples \(\mathrm{INJ }_{2} (2,5)\) and \(\mathrm{INJ }_{2}(3,5)\) . Hence, the overwhelming majority of our graphs is not Cayley.     

Isomorphisms between Jacobson graphs

Let \(R\) be a commutative ring with a non-zero identity and \(\mathfrak {J}_R\) be its Jacobson graph. We show that if \(R\) and \(R'\) are finite commutative rings, then \(\mathfrak {J}_R\cong \mathfrak {J}_{R'}\) if and only if \(|J(R)|=|J(R')|\) and \(R/J(R)\cong R'/J(R')\) . Also, for a Jacobson graph \(\mathfrak {J}_R\) , we obtain the structure of group \(\mathrm {Aut}(\mathfrak {J}_R)\) of all automorphisms of \(\mathfrak {J}_R\) and prove that under some conditions two semi-simple rings \(R\) and \(R'\) are isomorphic if and only if \(\mathrm {Aut}(\mathfrak {J}_R)\cong \mathrm {Aut}(\mathfrak {J}_{R'})\) .     

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.     

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.     

Completely regular clique graphs

Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, if there is a collection \(\mathcal{C}\) of completely regular cliques of size s+1 such that every edge is contained in exactly c members of  \(\mathcal{C}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph.     

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

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

Randomized large distortion dimension reduction

Consider a random matrix \(H:{\mathbb {R}}^{n}\longrightarrow {\mathbb {R}}^{m}\) . Let \(D\ge 2\) and let \(\{W_l\}_{l=1}^{p}\) be a set of \(k\) -dimensional affine subspaces of \({\mathbb {R}}^{n}\) . We ask what is the probability that for all \(1\le l\le p\) and \(x,y\in W_l\) , $$\begin{aligned} \Vert x-y\Vert _2\le \Vert Hx-Hy\Vert _2\le D\Vert x-y\Vert _2. \end{aligned}$$ We show that for \(m=O\big (k+\frac{\ln {p}}{\ln {D}}\big )\) and a variety of different classes of random matrices \(H\) , which include the class of Gaussian matrices, existence is assured and the probability is very high. The estimate on \(m\) is tight in terms of \(k,p,D\) .     

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.     

A Faster Algorithm for Computing Motorcycle Graphs

We present a new algorithm for computing motorcycle graphs that runs in \(O(n^{4/3+\varepsilon })\) time for any \(\varepsilon >0\) , improving on all previously known algorithms. The main application of this result is to computing the straight skeleton of a polygon. It allows us to compute the straight skeleton of a non-degenerate polygon with \(h\) holes in \(O(n \sqrt{h+1} \log ^2 n+n^{4/3+\varepsilon })\) expected time. If all input coordinates are \(O(\log n)\) -bit rational numbers, we can compute the straight skeleton of a (possibly degenerate) polygon with \(h\) holes in \(O(n \sqrt{h+1}\log ^3 n)\) expected time. In particular, it means that we can compute the straight skeleton of a simple polygon in \(O(n\log ^3n)\) expected time if all input coordinates are \(O(\log n)\) -bit rationals, while all previously known algorithms have worst-case running time \(\omega (n^{3/2})\) .     

Minimum total coloring of planar graph

Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is familiar to us by the name of “total coloring”. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements receive the same color. In other words, total chromatic number of \(G\) is the minimum number of disjoint vertex independent sets covering a total graph of \(G\) . Here, let \(G\) be a planar graph with \(\varDelta \ge 8\) . We proved that if for every vertex \(v\in V\) , there exists two integers \(i_{v},j_{v} \in \{3,4,5,6,7,8\}\) such that \(v\) is not incident with intersecting \(i_v\) -cycles and \(j_v\) -cycles, then the vertex chromatic number of total graph of \(G\) is \(\varDelta +1\) , i.e., the total chromatic number of \(G\) is \(\varDelta +1\) .     

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.     

Large collections of curves pairwise intersecting exactly once

Let \(\Omega =(\omega _{j})_{j\in I}\) be a maximum size collection of pairwise non-isotopic simple closed curves on the closed, orientable, genus \(g\) surface \(S_{g}\) , such that \(\omega _{i}\) and \(\omega _{j}\) intersect exactly once for \(i\ne j\) . We show that for \(g\ge 3\) , there exists atleast two such collections up to the action of the mapping class group, answering a question posed by Malestein, Rivin and Theran. As a consequence, we show that the automorphism group of the systole graph for \(S_{g}, g\ge 3\) (whose vertices are isotopy classes of simple closed curves, and whose edges correspond to pairs of curve intersecting once) does not act transitively on maximal complete subgraphs.     

The {\mathcal {A}}-Truncated K-Moment Problem

Let \({\mathcal {A}}\subseteq {\mathbb {N}}^n\) be a finite set, and \(K\subseteq {\mathbb {R}}^n\) be a compact semialgebraic set. An \({\mathcal {A}}\) -truncated multisequence ( \({\mathcal {A}}\) -tms) is a vector \(y=(y_{\alpha })\) indexed by elements in \({\mathcal {A}}\) . The \({\mathcal {A}}\) -truncated \(K\) -moment problem ( \({\mathcal {A}}\) -TKMP) concerns whether or not a given \({\mathcal {A}}\) -tms \(y\) admits a \(K\) -measure \(\mu \) , i.e., \(\mu \) is a nonnegative Borel measure supported in \(K\) such that \(y_\alpha = \int _K x^\alpha \mathtt {d}\mu \) for all \(\alpha \in {\mathcal {A}}\) . This paper proposes a numerical algorithm for solving \({\mathcal {A}}\) -TKMPs. It aims at finding a flat extension of \(y\) by solving a hierarchy of semidefinite relaxations \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) for a moment optimization problem, whose objective \(R\) is generated in a certain randomized way. If \(y\) admits no \(K\) -measures and \({\mathbb {R}}[x]_{{\mathcal {A}}}\) is \(K\) -full (there exists \(p \in {\mathbb {R}}[x]_{{\mathcal {A}}}\) that is positive on \(K\) ), then \((\mathtt {SDR})_k\) is infeasible for all \(k\) big enough, which gives a certificate for the nonexistence of representing measures. If \(y\) admits a \(K\) -measure, then for almost all generated \(R\) , this algorithm has the following properties: i) we can asymptotically get a flat extension of \(y\) by solving the hierarchy \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) ; ii) under a general condition that is almost sufficient and necessary, we can get a flat extension of \(y\) by solving \((\mathtt {SDR})_k\) for some \(k\) ; iii) the obtained flat extensions admit a \(r\) -atomic \(K\) -measure with \(r\le |{\mathcal {A}}|\) . The decomposition problems for completely positive matrices and sums of even powers of real linear forms, and the standard truncated \(K\) -moment problems, are special cases of \({\mathcal {A}}\) -TKMPs. They can be solved numerically by this algorithm.     

Classical limit of the tensor product of holomorphic discrete series representations

For three coadjoint orbits \(\mathcal {O}_1, \mathcal {O}_2\) and \(\mathcal {O}_3\) in \(\mathfrak {g}^*\) , the Corwin–Greenleaf function \(n(\mathcal {O}_1 \times \mathcal {O}_2, \mathcal {O}_3)\) is given by the number of \(G\) -orbits in \(\{(\lambda , \mu ) \in \mathcal {O}_1 \times \mathcal {O}_2 \, : \, \lambda + \mu \in \mathcal {O}_3 \}\) under the diagonal action. In the case where \(G\) is a simple Lie group of Hermitian type, we give an explicit formula of \(n(\mathcal {O}_1 \times \mathcal {O}_2, \mathcal {O}_3)\) for coadjoint orbits \(\mathcal {O}_1\) and \(\mathcal {O}_2\) that meet \(\left( [\mathfrak {k}, \mathfrak {k}] + \mathfrak {p}\right) ^{\perp }\) , and show that the formula is regarded as the ‘classical limit’ of a special case of Kobayashi’s multiplicity-free theorem (Progr. Math. 2007) in the branching law to symmetric pairs.     

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.     

Divide and Conquer Roadmap for Algebraic Sets

Let \(\mathrm{R}\) be a real closed field and \(\hbox {D}\subset \mathrm{R}\) an ordered domain. We describe an algorithm that given as input a polynomial \(P \in \hbox {D}[ X_{1} , \ldots ,X_{{ k}} ]\) and a finite set, \(\mathcal {A}= \{ p_{1} , \ldots ,p_{m} \}\) , of points contained in \(V= {\mathrm{{Zer}}} ( P, \mathrm{R}^{{ k}})\) described by real univariate representations, computes a roadmap of \(V\) containing \(\mathcal {A}\) . The complexity of the algorithm, measured by the number of arithmetic operations in \(\hbox {D}\) , is bounded by \(\big ( \sum _{i=1}^{m} D^{O ( \log ^{2} ( k ) )}_{i} +1 \big ) ( k^{\log ( k )} d )^{O ( k\log ^{2} ( k ))}\) , where \(d= \deg ( P )\) and \(D_{i}\) is the degree of the real univariate representation describing the point \(p_{i}\) . The best previous algorithm for this problem had complexity card \(( \mathcal {A} )^{O ( 1 )} d^{O ( k^{3/2} )}\) (Basu et al., ArXiv, 2012), where it is assumed that the degrees of the polynomials appearing in the representations of the points in \(\mathcal {A}\) are bounded by \(d^{O ( k )}\) . As an application of our result we prove that for any real algebraic subset \(V\) of \(\mathbb {R}^{k}\) defined by a polynomial of degree \(d\) , any connected component \(C\) of \(V\) contained in the unit ball, and any two points of \(C\) , there exists a semi-algebraic path connecting them in \(C\) , of length at most \(( k ^{\log (k )} d )^{O ( k\log ( k ) )}\) , consisting of at most \(( k ^{\log (k )} d )^{O ( k\log ( k ) )}\) curve segments of degrees bounded by \(( k ^{\log ( k )} d )^{O ( k \log ( k) )}\) . While it was known previously, by a result of D’Acunto and Kurdyka (Bull Lond Math Soc 38(6):951–965, 2006), that there always exists a path of length \(( O ( d ) )^{k-1}\) connecting two such points, there was no upper bound on the complexity of such a path.     

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

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.     

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.