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

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.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

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.     

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.     

No-three-in-line problem on a torus: Periodicity

Let ${\tau }_{m,n}$ denote the maximal number of points on the discrete torus (discrete toric grid) of sizes $m\times n$ with no three collinear points. The value ${\tau }_{m,n}$ is known for the case where $gcd(m,n)$ is prime. It is also known that ${\tau }_{m,n}\le 2gcd(m,n)$. In this paper we generalize some of the known tools for determining ${\tau }_{m,n}$ and also show some new. Using these tools we prove that the sequence ${\left({\tau }_{z,n}\right)}_{n\in \mathbb{N}}$ is periodic for all fixed $z>1$. In general, we do not know the period; however, if $z=p^a$ for $p$ prime, then we can bound it. We prove that ${\tau }_{p^a,p^{(a?1)p+2}}=2p^a$ which implies that the period for the sequence is $p^b$, where $b$ is at most $(a?1)p+2$.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

Sharp upper bounds of the spectral radius of a graph

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges. The spectral radius $\rho \left(G\right)$ of $G$ is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of $\rho \left(G\right)$ which improves some known bounds: If $\frac{(k?2)(k?3)}{2}\le m?n\le \frac{k(k?3)}{2}$, where $k(3\le k\le n)$ is an integer, then $\rho \left(G\right)\le \sqrt{2m?n?k+\frac{5}{2}+\sqrt{2m?2n+\frac{9}{4}}}.$The equality holds if and only if $G$ is a complete graph $K_n$ or $K_4?e$, where $K_4?e$ is the graph obtained from $K_4$ by deleting some edge $e$.     

Permutations with small maximal k-consecutive sums

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i?{\sum }_{j=0}^{k?1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $\mathsf{msum}(n,k)?min\left\{max\{s_i:i=1,\dots ,n\}?\frac{k(n+1)}{2}:\pi \in S_n\right\},$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathsf{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathsf{msum}(n,3)$, $\mathsf{msum}(n,4)$ and $\mathsf{msum}(n,6)$ for any $n$.     

Sharp non-asymptotic concentration inequalities for the approximation of the invariant distribution of a diffusion

Let ${\left(Y_t\right)}_{t\ge 0}$ be an ergodic diffusion with invariant distribution $\nu$. Consider the empirical measure ${\nu }_n≔{\left({\sum }_{k=1}^n{\gamma }_k\right)}^{-1}{\sum }_{k=1}^n{\gamma }_k{\delta }_{X_{k-1}}$ where ${\left(X_k\right)}_{k\ge 0}$ is an Euler scheme with decreasing steps ${\left({\gamma }_k\right)}_{k\ge 0}$ which approximates ${\left(Y_t\right)}_{t\ge 0}$. Given a test function $f$, we obtain sharp concentration inequalities for ${\nu }_n\left(f\right)-\nu \left(f\right)$ which improve the results in Honoré et al. (2019). Our hypotheses on the test function $f$ cover many real applications: either $f$ is supposed to be a coboundary of the infinitesimal generator of the diffusion, or $f$ is supposed to be Lipschitz.