Standing waves for the NLS on the double-bridge graph and a rational–irrational dichotomy

We study standing waves of NLS equation posed on the double-bridge graph: two semi-infinite half-lines attached at a circle. At the two vertices Kirchhoff boundary conditions are imposed. The configuration of the graph is characterized by two lengths, $L_1$ and $L_2$. We study the solutions with possibly nontrivial components on the half-lines and a cnoidal component on the circle. The problem is equivalent to a nonlinear boundary value problem in which the boundary condition depends on the spectral parameter ω. After classifying the solutions with rational $L_1/L_2$, we turn to $L_1/L_2$ irrational showing that there exist standing waves only in correspondence to a countable set of negative frequencies ${\omega }_n$. Moreover we show that the frequency sequence admits cluster points and any negative real number can be a limit point of frequencies choosing a suitable irrational geometry $L_1/L_2$. These results depend on basic properties of diophantine approximation of real numbers.     

Schmidt representation of bilinear operators on Hilbert spaces

Current work defines Schmidt representation of a bilinear operator $T:H_1\times H_2\to K$, where $H_1,H_2$ and $K$ are separable Hilbert spaces. Introducing the concept of singular value and ordered singular value, we prove that if $T$ is compact, and its singular values are ordered, then $T$ has a Schmidt representation on real Hilbert spaces. We prove that the hypothesis of existence of ordered singular values is fundamental.     

Separable discrete functions: Recognition and sufficient conditions

A discrete function of $n$ variables is a mapping $g:X_1\times \dots \times X_n\to A$, where $X_1,\dots ,X_n$, and $A$ are arbitrary finite sets. Function $g$ is called separable if there exist $n$ functions $g_i:X_i\to A$ for $i=1,\dots ,n$, such that for every input $x_1,\dots ,x_n$ the function $g(x_1,\dots ,x_n)$ takes one of the values $g_1\left(x_1\right),\dots ,g_n\left(x_n\right)$. Given a discrete function $g$, it is an interesting problem to ask whether $g$ is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of $n$ variables is known only for $n=2$. In this paper we will show that a slightly more general recognition problem, when $g$ is not fully but only partially defined, is NP-complete for $n\ge 3$. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for $n\ge 4$.The general recognition problem contains the above mentioned special case for $n=2$. This case is well-studied in the context of game theory, where (separable) discrete functions of $n$ variables are referred to as (assignable) $n$-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of $n$ variables for any $n$, thus generalizing the above result known for $n=2$. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function $g$ of $n$ variables one can construct separating functions $g_1,\dots ,g_n$ in polynomial time with respect to the size of the input function.     

Linearity and classification of ZpZp2-linear generalized Hadamard codes

The ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive codes are subgroups of ${\mathbb{Z}}_p^{{\alpha }_1}\times {\mathbb{Z}}_{p^2}^{{\alpha }_2}$, and can be seen as linear codes over ${\mathbb{Z}}_p$ when ${\alpha }_2=0$, ${\mathbb{Z}}_{p^2}$-additive codes when ${\alpha }_1=0$, or ${\mathbb{Z}}_2{\mathbb{Z}}_4$-additive codes when $p=2$. A ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear generalized Hadamard (GH) code is a GH code over ${\mathbb{Z}}_p$ which is the Gray map image of a ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive code. Recursive constructions of ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive GH codes of type $({\alpha }_1,{\alpha }_2;t_1,t_2)$ with $t_1,t_2\ge 1$ are known. In this paper, we generalize some known results for ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes with $p=2$ to any $p\ge 3$ prime when ${\alpha }_1\ne 0$, and then we compare them with the ones obtained when ${\alpha }_1=0$. First, we show for which types the corresponding ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes are nonlinear over ${\mathbb{Z}}_p$. Then, for these codes, we compute the kernel and its dimension, which allow us to classify them completely. Moreover, by computing the rank of some of these codes, we show that, unlike ${\mathbb{Z}}_4$-linear Hadamard codes, the ${\mathbb{Z}}_{p^2}$-linear GH codes are not included in the family of ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes with ${\alpha }_1\ne 0$ when $p\ge 3$ prime. Indeed, there are some families with infinite nonlinear ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes, where the codes are not equivalent to any ${\mathbb{Z}}_{p^s}$-linear GH code with $s\ge 2$.     

On the structure of certain valued fields

In this article, we study the structure of finitely ramified mixed characteristic valued fields. For any two complete discrete valued fields $K_1$ and $K_2$ of mixed characteristic with perfect residue fields, we show that if the n-th residue rings are isomorphic for each $n\ge 1$, then $K_1$ and $K_2$ are isometric and isomorphic. More generally, for $n_1\ge 1$, there is $n_2$ depending only on the ramification indices of $K_1$ and $K_2$ such that any homomorphism from the $n_1$-th residue ring of $K_1$ to the $n_2$-th residue ring of $K_2$ can be lifted to a homomorphism between the valuation rings. Moreover, we get a functor from the category of certain principal Artinian local rings of length n to the category of certain complete discrete valuation rings of mixed characteristic with perfect residue fields, which naturally generalizes the functorial property of unramified complete discrete valuation rings. Our lifting result improves Basarab's relative completeness theorem for finitely ramified henselian valued fields, which solves a question posed by Basarab, in the case of perfect residue fields.     

Almost perfect nonlinear families which are not equivalent to permutations

An important problem on almost perfect nonlinear (APN) functions is the existence of APN permutations on even-degree extensions of ${\mathbb{F}}_2$ larger than 6. Browning et al. (2010) gave the first known example of an APN permutation on the degree-6 extension of ${\mathbb{F}}_2$. The APN permutation is CCZ-equivalent to the previously known quadratic Kim κ-function (Browning et al. (2009)). Aside from the computer based CCZ-inequivalence results on known APN functions on even-degree extensions of ${\mathbb{F}}_2$ with extension degrees less than 12, no theoretical CCZ-inequivalence result on infinite families is known. In this paper, we show that Gold and Kasami APN functions are not CCZ-equivalent to permutations on infinitely many even-degree extensions of ${\mathbb{F}}_2$. In the Gold case, we show that Gold APN functions are not equivalent to permutations on any even-degree extension of ${\mathbb{F}}_2$, whereas in the Kasami case we are able to prove inequivalence results for every doubly-even-degree extension of ${\mathbb{F}}_2$.     

Perfect matchings extend to two or more hamiltonian cycles in hypercubes

Kreweras conjectured that every perfect matching of a hypercube $Q_n$ for $n\ge 2$ can be extended to a hamiltonian cycle of $Q_n$. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of $Q_n$ for $n\ge 2$ can be extended to two or more hamiltonian cycles of $Q_n$. In this paper, we prove that every perfect matching of $Q_n$ for $n\ge 4$ can be extended to at least $2^{2^{n?4}}$ different hamiltonian cycles of $Q_n$.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Context-free grammars,generating functions and combinatorial arrays

Let ${\left[R_{n,k}\right]}_{n,k\ge 0}$ be an array of nonnegative numbers satisfying the recurrence relation $R_{n,k}=(a_{1}n+a_{2}k+a_3)R_{n-1,k}+(b_{1}n+b_{2}k+b_3)R_{n-1,k-1}+(c_{1}n+c_{2}k+c_3)R_{n-1,k-2}$ with $R_{0,0}=1$ and $R_{n,k}=0$ unless $0\le k\le n$. In this paper, we first prove that the array ${\left[R_{n,k}\right]}_{n,k\ge 0}$ can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of ${\left[R_{n,k}\right]}_{n,k\ge 0}$. Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type $B$, and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong $q$-log-convexity of some generating functions.     

ℓ1-symmetric vector random fields

This paper studies the properties of ${?}_1$-symmetric vector random fields in ${\mathbb{R}}^d$, whose direct/cross covariances are functions of ${?}_1$-norm. The spectral representation and a turning bands expression of the covariance matrix function are derived for an ${?}_1$-symmetric vector random field that is mean square continuous. We also establish an integral relationship between an ${?}_1$-symmetric covariance matrix function and an isotropic one. In addition, a simple but efficient approach is proposed to construct the ${?}_1$-symmetric random field in ${\mathbb{R}}^d$, whose univariate marginal distributions may be taken as arbitrary infinitely divisible distribution with finite variance.     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.