Projective well orders and coanalytic witnesses

We further develop a forcing notion known as Coding with Perfect Trees and show that this poset preserves, in a strong sense, definable P-points, definable tight MAD families and definable selective independent families. As a result, we obtain a model in which $\mathfrak{a}=\mathfrak{u}=\mathfrak{i}={\mathrm{?}}_1<2^{{\mathrm{?}}_0}={\mathrm{?}}_2$, each of $\mathfrak{a}$, $\mathfrak{u}$, $\mathfrak{i}$ has a ${\mathrm{\Pi }}_1^1$ witness and there is a ${\mathrm{\Delta }}_3^1$ well-order of the reals. Note that both the complexity of the witnesses of the above combinatorial cardinal characteristics, as well as the complexity of the well-order are optimal. In addition, we show that the existence of a ${\mathrm{\Delta }}_3^1$ well-order of the reals is consistent with $\mathfrak{c}={\mathrm{?}}_2$ and each of the following: $\mathfrak{a}=\mathfrak{u}<\mathfrak{i}$, $\mathfrak{a}=\mathfrak{i}<\mathfrak{u}$, $\mathfrak{a}<\mathfrak{u}=\mathfrak{i}$, where the smaller cardinal characteristics have co-analytic witnesses.Our methods allow the preservation of only sufficiently definable witnesses, which significantly differs from other preservation results of this type.     

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.     

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.     

On the asymptotic growth of bipartite graceful permutations

We give exact growth rates for the number of bipartite graceful permutations of the symbols $\{0,1,\dots ,n?1\}$ that start with $a$ for $a\le 14$ (equivalently, $\alpha$-labelings of paths with $n$ vertices that have $a$ as a pendant label). In particular, when $a=14$ the growth is asymptotically like ${\lambda }^n$ for $\lambda \approx 3.461$. The number of graceful permutations of length $n$ grows at least this fast, improving on the best existing asymptotic lower bound of $2.37^n$. Combined with existing theory, this improves the known lower bounds on the number of Hamiltonian decompositions of the complete graph $K_{2n+1}$ and on the number of cyclic oriented triangular embeddings of $K_{12s+3}$ and $K_{12s+7}$. We also give the first exponential lower bound on the number of R-sequencings of ${\mathbb{Z}}_{2n+1}$.     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).     

Erdős–Gallai stability theorem for linear forests

The Erd?s–Gallai Theorem states that every graph of average degree more than $l?2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd?s–Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=\left({?}_{i=1}^k{P}_{2a_i}\right)?\left({?}_{i=1}^l{P}_{2b_i+1}\right)$ be $k+l$ disjoint paths of order $2a_1,\dots ,2a_k,2b_1+1,\dots ,2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\ge 2$. If the minimum degree $\delta \left(G\right)\ge {\sum }_{i=1}^k{a}_i+{\sum }_{i=1}^l{b}_i?1$, then $F?G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.     

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 three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Balls,bins, and embeddings of partial k-star designs

Define a $k$-star to be the complete bipartite graph $K_{1,k}$. In a 2014 article, Hoffman and Roberts prove that a partial $k$-star decomposition of $K_n$ can be embedded in a $k$-star decomposition of $K_{n+s}$ where $s$ is at most $7k?4$ if $k$ is odd and $8k?4$ if $k$ is even. In our work, we offer a straightforward construction for embedding partial $k$-star designs and lower these bounds to $3k?2$ and $4k?2$, respectively.     

Matching in 3-uniform hypergraphs

A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. We use $E_3(2d?1,n?2d+1)$ to denote the 3-uniform hypergraph whose vertex set can be partitioned into two vertex classes $V_1$ and $V_2$ of size $2d?1$ and $n?2d+1$, respectively, and whose edge set consists of all the triples containing at least two vertices of $V_1$. Let $H$ be a 3-uniform hypergraph of order $n\ge 13d$ with no isolated vertex and $\text{deg}\left(u\right)+\text{deg}\left(v\right)>2\left(\left(\genfrac{}{}{0ex}{}{n?1}{2}\right)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)\right)$ for any two adjacent vertices $u,v\in V\left(H\right)$. In this paper, we show that $H$ contains a matching of size $d$ if and only if $H$ is not a subgraph of $E_3(2d?1,n?2d+1)$. This result improves our previous one in Zhang and Lu (2018).     

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.     

Explicit computation of some families of Hurwitz numbers

We compute the number of (weak) equivalence classes of branched covers from a surface of genus $g$ to the sphere, with 3 branching points, degree $2k$, and local degrees over the branching points of the form $(2,\dots ,2)$, $(2h+1,1,2,\dots ,2)$, $\pi ={\left(d_i\right)}_{i=1}^{\ell }$, for several values of $g$ and $h$. We obtain explicit formulae of arithmetic nature in terms of the local degrees $d_i$. Our proofs employ a combinatorial method based on Grothendieck’s dessins d’enfant.     

On the maximum number of minimum dominating sets in forests

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $\gamma$ has at most $2^{\gamma }$ minimum dominating sets. Bień gave a counterexample, which allows us to construct forests with domination number $\gamma$ and $2.0598^{\gamma }$ minimum dominating sets. We show that every forest with domination number $\gamma$ has at most $2.4606^{\gamma }$ minimum dominating sets, and that every tree with independence number $\alpha$ has at most $2^{\alpha -1}+1$ maximum independent sets.     

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