Bounds for the Graham–Pollak theorem for hypergraphs

Let $f_r\left(n\right)$ represent the minimum number of complete $r$-partite $r$-graphs required to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. The Graham–Pollak theorem states that $f_2\left(n\right)=n?1$. An upper bound of $(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was known. Recently this was improved to $\frac{14}{15}(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ for even $r\ge 4$. A bound of $\left[\frac{r}{2}{\left(\frac{14}{15}\right)}^{\frac{r}{4}}+o\left(1\right)\right](1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was also proved recently. Let $c_r$ be the limit of $\frac{f_r\left(n\right)}{\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)}$ as $n\to \infty$. The smallest odd $r$ for which $c_r<1$ that was known was for $r=295$. In this note we improve this to $c_{113}<1$ and also give better upper bounds for $f_r\left(n\right)$, for small values of even $r$.     

Hankel determinants for convolution powers of Catalan numbers

The Hankel determinants ${\left(\frac{r}{2(i+j)+r}\left(\genfrac{}{}{0ex}{}{2(i+j)+r}{i+j}\right)\right)}_{0\le i,j\le n?1}$ of the convolution powers of Catalan numbers were considered by Cigler and Krattenthaler. We evaluate these determinants for $r\le 31$ by finding shifted periodic continued fractions, which arose in application of Sulanke and Xin’s continued fraction method. These include some of the conjectures of Cigler as special cases. We also conjecture a polynomial characterization of these determinants. The same technique is used to evaluate the Hankel determinants ${\left(\left(\genfrac{}{}{0ex}{}{2(i+j)+r}{i+j}\right)\right)}_{0\le i,j\le n?1}$. Similar results are obtained.     

Behavior of the Hermite sheet with respect to theHurst index

We consider a $d$-parameter Hermite process with Hurst index $\mathbf{H}=(H_1,..,H_d)\in {\left(\frac{1}{2},1\right)}^d$ and we study its limit behavior in distribution when the Hurst parameters $H_i,i=1,..,d$ (or a part of them) converge to $\frac{1}{2}$ and/or 1. The limit obtained is Gaussian (when at least one parameter tends to $\frac{1}{2}$) and non-Gaussian (when at least one-parameter tends to 1 and none converges to $\frac{1}{2}$).     

On a sum involving the Euler totient function

In this short note, we prove that $\frac{4}{{\pi }^2}xlogx+O\left(x\right)?\sum _{n?x}\phi \left(\left[\frac{x}{n}\right]\right)?\left(\frac{1}{3}+\frac{4}{{\pi }^2}\right)xlogx+O\left(x\right),$ for $x\to \infty$, where $\phi \left(n\right)$ is the Euler totient function and $\left[t\right]$ is the integral part of real $t$. This improves recent results of Bordellès–Heyman–Shparlinski and of Dai–Pan.     

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

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

A plurality problem with three colors and query size three

The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color class is strictly larger than any other color class. Questioner asks a triplet (or a k-set in general), and Adversary as an answer gives the partition of the triplet (or the k-set) into color classes. Questioner wants to find a plurality ball as soon as possible or show that there is no such ball, while Adversary wants to postpone this.We denote by $A_p(n,k)$ the largest number of queries needed to ask in the worst case if both play optimally. We provide an almost precise result in the case of even n by proving that for $n\ge 4$ even we have$\frac{3}{4}n?2\le A_p(n,3)\le \frac{3}{4}n?\frac{1}{2},$ and for $n\ge 3$ odd we have$\frac{3}{4}n?O(\log ?n)\le A_p(n,3)\le \frac{3}{4}n?\frac{1}{2}.$We also prove some bounds on the number of queries needed to ask in the case $k\ge 3$.     

Enumerative properties and cube polynomials of Tribonacci cubes

Tribonacci cubes ${\Gamma }_n^{\left(3\right)}$are induced subgraphs of $Q_n$, obtained by removing all the vertices that contain more than two consecutive 1’s. In the present work, we give some enumerative properties related to ${\Gamma }_n^{\left(3\right)}$. We show that the number of vertices of weight $w$ in ${\Gamma }_n^{\left(3\right)}$is ${\sum }_{j=0}^{n-w+1}\left(\genfrac{}{}{0ex}{}{n-w+1}{j}\right)\left(\genfrac{}{}{0ex}{}{j}{w-j}\right)$ and express the number of edges of these graphs in terms of convolved Tribonacci numbers. We investigate the cube polynomials of Tribonacci cubes and determine the corresponding generating function. Finally, we give a formula for the number of induced $k$-cubes in ${\Gamma }_n^{\left(3\right)}$.     

Remarks on the distribution of colors in Gallai colorings

A Gallai coloring of a complete graph $K_n$ is an edge coloring without triangles colored with three different colors. A sequence $e_1\ge \cdots \ge e_k$ of positive integers is an $(n,k)$-sequence if ${\sum }_{i=1}^k{e}_i=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. An $(n,k)$-sequence is a G-sequence if there is a Gallai coloring of $K_n$ with $k$ colors such that there are $e_i$ edges of color $i$ for all $i,1\le i\le k$. Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer $k\ge 3$ there exists an integer $g\left(k\right)$ such that every $(n,k)$-sequence is a G-sequence if and only if $n\ge g\left(k\right)$. They showed that $g\left(3\right)=5,g\left(4\right)=8$ and $2k-2\le g\left(k\right)\le 8k^2+1$.We show that $g\left(5\right)=10$ and give almost matching lower and upper bounds for $g\left(k\right)$ by showing that with suitable constants $\alpha ,\beta >0$, $\frac{\alpha k^{1.5}}{lnk}\le g\left(k\right)\le \beta k^{1.5}$ for all sufficiently large $k$.     

Approximating the multiple-depot multiple-terminal Hamiltonian path problem

In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where $m$ salesmen are initially located at different depots and finally stopped at different terminals. To the best of our knowledge, only 2-approximation algorithm is available in the literature. For arbitrary $m⩾2$, we first present a Christofides-like heuristic with a tight approximation ratio of $2-\frac{1}{2m+1}$. Besides, we also develop a $(\frac{5}{3}+ϵ)$-approximation algorithm by divide-and-conquer technique. The $(\frac{5}{3}+ϵ)$-approximation algorithm runs in polynomial time for fixed $m$ and $ϵ$.     

Average degrees of edge-chromatic critical graphs

Let $G$ be a simple graph, and let $\Delta \left(G\right)$, $\overline{d}\left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree, the average degree and the chromatic index of $G$, respectively. We called $G$ edge-$\Delta$-critical if ${\chi }^{\prime }\left(G\right)=\Delta \left(G\right)+1$ and ${\chi }^{\prime }\left(H\right)\le \Delta \left(G\right)$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is an edge-$\Delta$-critical graph of order $n$, then $\overline{d}\left(G\right)\ge \Delta \left(G\right)?1+\frac{3}{n}$. We prove that for any edge-$\Delta$-critical graph $G$, $\stackrel{?}{d}\left(G\right)\ge min\left\{\frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1},\frac{3\Delta \left(G\right)}{4}?2\right\},$ that is, $\overline{d}\left(G\right)\ge \left\{\begin{array}{cc}\frac{3}{4}\Delta \left(G\right)?2\hfill & \text{if}\Delta \left(G\right)\le 75;\hfill \\ \frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1}\approx 0.7388\Delta \left(G\right)?1.153\hfill & \text{if}\Delta \left(G\right)\ge 76.\hfill \end{array}\right.$This result improves the best known bound $\frac{2}{3}(\Delta \left(G\right)+2)$ obtained by Woodall in 2007 for $\Delta \left(G\right)\ge 41$.     

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.