Sums of powers of Catalan triangle numbers

In this paper, we consider combinatorial numbers ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$, mentioned as Catalan triangle numbers where $C_{m,k}?\left(\genfrac{}{}{0ex}{}{m?1}{k}\right)?\left(\genfrac{}{}{0ex}{}{m?1}{k?1}\right)$. These numbers unify the entries of the Catalan triangles $B_{n,k}$ and $A_{n,k}$ for appropriate values of parameters $m$ and $k$, i.e., $B_{n,k}=C_{2n,n?k}$ and $A_{n,k}=C_{2n+1,n+1?k}$. In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers $C_n$ that is $C_{2n,n?1}=C_{2n+1,n}=C_n$.We present identities for sums (and alternating sums) of $C_{m,k}$, squares and cubes of $C_{m,k}$ and, consequently, for $B_{n,k}$ and $A_{n,k}$. In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$ and harmonic numbers ${\left(H_n\right)}_{n\ge 1}$. Finally, in the last section, new open problems and identities involving ${\left(C_n\right)}_{n\ge 0}$ are conjectured.     

Cycles with a chord in dense graphs

A cycle of order $k$ is called a $k$-cycle. A non-induced cycle is called a chorded cycle. Let $n$ be an integer with $n\ge 4$. Then a graph $G$ of order $n$ is chorded pancyclic if $G$ contains a chorded $k$-cycle for every integer $k$ with $4\le k\le n$. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order $n$ satisfying ${deg}_{G}u+{deg}_{G}v\ge n$ for every pair of nonadjacent vertices $u$,  $v$ in $G$ is chorded pancyclic unless $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, the Cartesian product of $K_3$ and $K_2$. They also conjectured that if $G$ is Hamiltonian, we can replace the degree sum condition with the weaker density condition $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph $G$ of order $n$ with $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ contains a $k$-cycle, then $G$ contains a chorded $k$-cycle, unless $k=4$ and $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, Then observing that $K_{\frac{n}{2},\frac{n}{2}}$ and $K_3\square K_2$ are exceptions only for $k=4$, we further relax the density condition for sufficiently large $k$.     

Sparse graphs of girth at least five are packable

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph $G$ with girth at least $5$ is packable.The conjecture was proved by Faudree et al. with the additional condition that $G$ has at most $\frac{6}{5}n?2$ edges. In this paper, for each integer $k\ge 3$, we prove that every non-star graph with girth at least $5$ and at most $\frac{2k?1}{k}n?{\alpha }_k\left(n\right)$ edges is packable, where ${\alpha }_k\left(n\right)$ is $o\left(n\right)$ for every $k$. This implies that the conjecture is true for sufficiently large planar graphs.     

Turán numbers for odd wheels

The Turán number $\text{ex}(n,G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A wheel$W_n$ is a graph on $n$ vertices obtained from a $C_{n?1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{n?1}$. We obtain two exact values for small wheels:

$\text{ex}(n,W_5)=?\frac{n^2}{4}+\frac{n}{2}?,$

$\text{ex}(n,W_7)=?\frac{n^2}{4}+\frac{n}{2}+1?.$

Given that $\text{ex}(n,W_6)$ is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound $\text{ex}(n,W_{2k+1})>?\frac{n^2}{4}?+?\frac{n}{2}?$ in general case.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.     

The smallest surface that contains all signed graphs on K4,n

Finding the smallest number of crosscaps that suffice to orientation-embed every edge signature of the complete bipartite graph $K_{m,n}$ is an open problem. In this paper that number for the complete bipartite graph $K_{4,n}$, $n\ge 4$, is determined by using diamond products of signed graphs. The number is $2?\frac{n?1}{2}?+1$, which is attained by $K_{4,n}$ with exactly 1 negative edge, except that when $n=4$, the number is 4, which is attained by $K_{4,4}$ with exactly 4 independent negative edges.     

On L-functions of certain exponential sums

Let ${\mathbb{F}}_q$ denote the finite field of order q of characteristic p. We study the p-adic valuations for zeros of L-functions associated with exponential sums of the following family of Laurent polynomials$f(x)=a_1{x}_{n+1}(x_1+\frac{1}{x_1})+\cdots +a_n{x}_{n+1}(x_n+\frac{1}{x_n})+a_{n+1}{x}_{n+1}+\frac{1}{x_{n+1}}$ where $a_i\in {\mathbb{F}}_q^{⁎}$, $i=1,2,\dots ,n+1$. When $n=2$, the estimate of the associated exponential sum appears in Iwaniecʼs work on small eigenvalues of the Laplace–Beltrami operator acting on automorphic functions with respect to the group ${\Gamma }_0(p)$, and Adolphson and Sperber gave complex absolute values for zeros of the corresponding L-function. Using the decomposition theory of Wan, we determine the generic Newton polygon (q-adic values of the reciprocal zeros) of the L-function. Working on the chain level version of Dworkʼs trace formula and using Wanʼs decomposition theory, we are able to give an explicit Hasse polynomial for the generic Newton polygon in low dimensions, i.e., $n⩽3$.