Maximal sets of Hamilton cycles in Knr;λ1,λ2

Let $K\left(n^r;{\lambda }_1,{\lambda }_2\right)$ be the $r$-partite multigraph in which each part has size $n$, where two vertices in the same part or different parts are joined by exactly ${\lambda }_1$ edges or ${\lambda }_2$ edges, respectively. It is proved that there exists a maximal set of $t$ edge-disjoint Hamilton cycles in $K\left(n^r;{\lambda }_1,{\lambda }_2\right)$ for ${\lambda }_{2}n\lfloor \frac{r+3}{4}\rfloor \le t\le min\left\{\lfloor \frac{{\lambda }_2{n}^2(r-1)}{2}\rfloor ,\lfloor \frac{{\lambda }_1(n-1)+{\lambda }_{2}n(r-1)}{2}\rfloor \right\}$, the upper bound being best possible. The results proved make use of the method of amalgamations.     

Construction and enumeration of left dihedral codes satisfying certain duality properties

Let ${\mathbb{F}}_q$ be the finite field of q elements and let $D_{2n}=〈x,y|x^n=1,y^2=1,yxy=x^{n?1}〉$ be the dihedral group of 2n elements. Left ideals of the group algebra ${\mathbb{F}}_q[D_{2n}]$ are known as left dihedral codes over ${\mathbb{F}}_q$ of length 2n, and abbreviated as left $D_{2n}$-codes. Let $\gcd (n,q)=1$. In this paper, we give an explicit representation for the Euclidean hull of every left $D_{2n}$-code over ${\mathbb{F}}_q$. On this basis, we determine all distinct Euclidean LCD codes and Euclidean self-orthogonal codes which are left $D_{2n}$-codes over ${\mathbb{F}}_q$. In particular, we provide an explicit representation and a precise enumeration for these two subclasses of left $D_{2n}$-codes and self-dual left $D_{2n}$-codes, respectively. Moreover, we give a direct and simple method for determining the encoder (generator matrix) of any left $D_{2n}$-code over ${\mathbb{F}}_q$, and present several numerical examples to illustrative our applications.     

The component counts of random functions

Consider functions $f:A\to A\cup C$, where A and C are disjoint finite sets. The weakly connected components of the digraph of such a function are cycles of rooted trees, as in random mappings, and isolated rooted trees. Let $n_1=|A|$ and $n_3=|C|$. When a function is chosen from all ${(n_1+n_3)}^{n_1}$ possibilities uniformly at random, then we find the following limiting behaviour as $n_1\to \infty$. If $n_3=o(n_1)$, then the size of the maximal mapping component goes to infinity almost surely; if $n_3～\gamma n_1$, $\gamma >0$ a constant, then process counting numbers of mapping components of different sizes converges; if $n_1=o(n_3)$, then the number of mapping components converges to 0 in probability. We get estimates on the size of the largest tree component which are of order $\log ?n_3$ when $n_3～\gamma n_1$ and constant when $n_3～n_1^{\alpha }$, $\alpha >1$. These results are similar to ones obtained previously for random injections, for which the weakly connected components are cycles and linear trees.     

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.     

Gaps in the number of generators of monomial Togliatti systems

Let $I_{d,n}?k[x_0,?,x_n]$ be a minimal monomial Togliatti system of forms of degree d. In [4], Mezzetti and Miró-Roig proved that the minimal number of generators $\mu (I_{d,n})$ of $I_{d,n}$ lies in the interval $[2n+1,\left(\begin{array}{c}n+d?1\\ n?1\end{array}\right)]$. In this paper, we prove that for $n\ge 4$ and $d\ge 3$, the integer values in $[2n+3,3n?1]$ cannot be realized as the number of minimal generators of a minimal monomial Togliatti system. We classify minimal monomial Togliatti systems $I_{d,n}?k[x_0,?,x_n]$ of forms of degree d with $\mu (I_{d,n})=2n+2$ or 3n (i.e. with the minimal number of generators reaching the border of the non-existence interval). Finally, we prove that for $n=4$, $d\ge 3$ and $\mu \in [9,\left(\begin{array}{c}d+3\\ 3\end{array}\right)]?\{11\}$ there exists a minimal monomial Togliatti system $I_{d,n}?k[x_0,?,x_n]$ of forms of degree d with $\mu (I_{n,d})=\mu$.     

Packed words and quotient rings

The coinvariant algebra is a quotient of the polynomial ring $\mathbb{Q}[x_1,\dots ,x_n]$ whose algebraic properties are governed by the combinatorics of permutations of length n. A word $w=w_1\dots w_n$ over the positive integers is packed if whenever $i>2$ appears as a letter of w, so does $i?1$. We introduce a quotient $S_n$ of $\mathbb{Q}[x_1,\dots ,x_n]$ which is governed by the combinatorics of packed words. We relate our quotient $S_n$ to the generalized coinvariant rings of Haglund, Rhoades, and Shimozono as well as the superspace coinvariant ring.     

Non parametric estimation of the diffusion coefficients of a diffusion with jumps

In this article, we consider a jump diffusion process ${\left(X_t\right)}_{t\ge 0}$, with drift function $b$, diffusion coefficient $\sigma$ and jump coefficient ${\xi }^2$. This process is observed at discrete times $t=0,\Delta ,\dots ,n\Delta$. The sampling interval $\Delta$ tends to 0 and the time interval $n\Delta$ tends to infinity. We assume that ${\left(X_t\right)}_{t\ge 0}$ is ergodic, strictly stationary and exponentially $\beta$-mixing. We use a penalized least-square approach to compute adaptive estimators of the functions ${\sigma }^2+{\xi }^2$ and ${\sigma }^2$. We provide bounds for the risks of the two estimators.     

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.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Irreducible polynomials over F2r with three prescribed coefficients

For any positive integers $n\ge 3$ and $r\ge 1$, we prove that the number of monic irreducible polynomials of degree n over ${\mathbb{F}}_{2^r}$ in which the coefficients of $T^{n-1}$, $T^{n-2}$ and $T^{n-3}$ are prescribed has period 24 as a function of n, after a suitable normalization. A similar result holds over ${\mathbb{F}}_{5^r}$, with the period being 60. We also show that this is a phenomena unique to characteristics 2 and 5. The result is strongly related to the supersingularity of certain curves associated with cyclotomic function fields, and in particular it complements an equidistribution result of Katz.     

Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.