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.     

On the local geometry of graphs in terms of their spectra

In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose $G_1,G_2,G_3,\dots$ is a sequence of finite and connected graphs that share a common universal cover $T$ and such that the proportion of eigenvalues of $G_n$ that lie within the support of the spectrum of $T$ tends to 1 in the large $n$ limit. This is a weak notion of being Ramanujan. We prove such a sequence of graphs is asymptotically locally tree-like. This is deduced by way of an analogous theorem proved for certain infinite sofic graphs and unimodular networks, which extends results for regular graphs and certain infinite Cayley graphs.     

Decomposition of complete equipartite graphs into paths and cycles of length 2p

Let $P_k$ and $C_k$ respectively denote a path and a cycle on k vertices. In this paper, we give necessary and sufficient conditions for the existence of a complete $\{P_{2p+1},C_{2p}\}$-decomposition of even regular complete equipartite graphs for all prime p.     

On color isomorphic subdivisions

Given a graph H and an integer $k?2$, let $f_k(n,H)$ be the smallest number of colors C such that there exists a proper edge-coloring of the complete graph $K_n$ with C colors containing no k vertex-disjoint color isomorphic copies of H. In this paper, we prove that $f_2(n,H_t)=\mathrm{\Omega }(n^{1+\frac{1}{2t?3}})$ where $H_t$ is the 1-subdivision of the complete graph $K_t$. This answers a question of Conlon and Tyomkyn (2021) [4].     

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

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.