[1, 2]-sets in graphs

A subset S⊆V$S\subseteq V$ in a graph G=(V,E)$G=(V,E)$ is a [j,k]$[j,k]$-set if, for every vertex v∈V?S$v\in V?S$, j≤|N(v)∩S|≤k$j\le |N\left(v\right)\cap S|\le k$ for non-negative integers j$j$ and k$k$, that is, every vertex v∈V?S$v\in V?S$ is adjacent to at least j$j$ but not more than k$k$ vertices in S$S$. In this paper, we focus on small j$j$ and k$k$, and relate the concept of [j,k]$[j,k]$-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k$k$-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G$G$, the restrained domination number is equal to the domination number of G$G$.     

Frobenius groups and retract rationality

Let k$k$ be any field, G$G$ be a finite group acting on the rational function field k(_xg:g∈G)$k(x_g:g\in G)$ by h⋅_xg=_xhg$h\cdot x_g=x_{hg}$ for any h,g∈G$h,g\in G$. Define k(G)=k(_xg:g∈G)^G$k\left(G\right)=k{(x_g:g\in G)}^G$. Noether’s problem asks whether k(G)$k\left(G\right)$ is rational (= purely transcendental) over k$k$. A weaker notion, retract rationality introduced by Saltman, is also very useful for the study of Noether’s problem. We prove that, if G$G$ is a Frobenius group with abelian Frobenius kernel, then k(G)$k\left(G\right)$ is retract k$k$-rational for any field k$k$ satisfying some mild conditions. As an application, we show that, for any algebraic number field k$k$, for any Frobenius group G$G$ with Frobenius complement isomorphic to S_L2(_F5)$S{L}_2\left({\mathbb{F}}_5\right)$, there is a Galois extension field K$K$ over k$k$ whose Galois group is isomorphic to G$G$, i.e. the inverse Galois problem is valid for the pair (G,k)$(G,k)$. The same result is true for any non-solvable Frobenius group if k(_ζ8)$k\left({\zeta }_8\right)$ is a cyclic extension of k$k$.     

Metric ultraproducts of finite simple groups

Some new results on metric ultraproducts of finite simple groups are presented. Suppose that G is such a group, defined in terms of a non-principal ultrafilter ω   on N$\mathbb{N}$ and a sequence (G_i)_i∈N${(G_i)}_{i\in \mathbb{N}}$ of finite simple groups, and that G is neither finite nor a Chevalley group over an infinite field. Then G is isomorphic to an ultraproduct of alternating groups or to an ultraproduct of finite simple classical groups. The isomorphism type of G determines which of these two cases arises, and, in the latter case, the ω  -limit of the characteristics of the groups G_i$G_i$. Moreover, G is a complete path-connected group with respect to the natural metric on G.     

Resolving sets for Johnson and Kneser graphs

A set of vertices S$S$ in a graph G$G$ is a resolving set   for G$G$ if, for any two vertices u,v$u,v$, there exists x∈S$x\in S$ such that the distances d(u,x)≠d(v,x)$d(u,x)\ne d(v,x)$. In this paper, we consider the Johnson graphs J(n,k)$J(n,k)$ and Kneser graphs K(n,k)$K(n,k)$, and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.     

A new upper bound on the acyclic chromatic indices of planar graphs

An acyclic edge coloring of a graph G$G$ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a^′(G)$a^{\prime }\left(G\right)$ of G$G$ is the smallest integer k$k$ such that G$G$ has an acyclic edge coloring using k$k$ colors. It was conjectured that a^′(G)≤Δ+2$a^{\prime }\left(G\right)\le \Delta +2$ for any simple graph G$G$ with maximum degree Δ$\Delta$. In this paper, we prove that if G$G$ is a planar graph, then a^′(G)≤Δ+7$a^{\prime }\left(G\right)\le \Delta +7$. This improves a result by Basavaraju et al. [M. Basavaraju, L.S. Chandran, N. Cohen, F. Havet, T. Müller, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math. 25 (2011) 463–478], which says that every planar graph G$G$ satisfies a^′(G)≤Δ+12$a^{\prime }\left(G\right)\le \Delta +12$.     

The stabilized set of p's in Krivine's theorem can be disconnected

For any closed subset F   of [1,∞]$[1,\infty ]$ which is either finite or consists of the elements of an increasing sequence and its limit, a reflexive Banach space X with a 1-unconditional basis is constructed so that in each block subspace Y of X  , _?p${?}_p$ is finitely block represented in Y   if and only if p∈F$p\in F$. In particular, this solves the question as to whether the stabilized Krivine set for a Banach space had to be connected. We also prove that for every infinite dimensional subspace Y of X there is a dense subset G of F such that the spreading models admitted by Y   are exactly the _?p${?}_p$ for p∈G$p\in G$.     

The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a,b}$a\oplus b=\min \{a,b\}$ and a⊗b=a+b$a\otimes b=a+b$. Let A be a tropical matrix and k   a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^m×k$B\in {\mathbf{R}}^{m\times k}$ and C∈R^k×n$C\in {\mathbf{R}}^{k\times n}$ satisfying B⊗C=A$B\otimes C=A$. We show that the TMF problem is NP-hard for every k≥7$k\ge 7$ fixed in advance, thus resolving a problem proposed by Barvinok in 1993.     

On the removal lemma for linear systems over Abelian groups

In this paper we present an extension of the removal lemma to integer linear systems over abelian groups. We prove that, if the k$k$-determinantal of an integer (k×m)$(k\times m)$ matrix A$A$ is coprime with the order n$n$ of a group G$G$ and the number of solutions of the system Ax=b$Ax=b$ with _x1∈_X1,…,_xm∈_Xm$x_1\in X_1,\dots ,x_m\in X_m$ is o(n^m−k)$o\left(n^{m-k}\right)$, then we can eliminate o(n)$o\left(n\right)$ elements in each set to remove all these solutions.     

Quasi-Banach spaces of almost universal disposition

We show that for each p∈(0,1]$p\in (0,1]$ there exists a separable p  -Banach space _Gp${\mathbb{G}}_p$ of almost universal disposition, that is, having the following extension property: for each ε>0$\epsilon >0$ and each isometric embedding g:X→Y$g:X\to Y$, where Y is a finite-dimensional p-Banach space and X   is a subspace of _Gp${\mathbb{G}}_p$, there is an ε  -isometry f:Y→_Gp$f:Y\to {\mathbb{G}}_p$ such that x=f(g(x))$x=f(g(x))$ for all x∈X$x\in X$.