Panchromatic 3-colorings of random hypergraphs

The paper deals with panchromatic 3-colorings of random hypergraphs. A vertex 3-coloring is said to be panchromatic for a hypergraph if every color can be found on every edge. Let $H(n,k,p)$ denote the binomial model of a random $k$-uniform hypergraph on $n$ vertices. For given fixed $c>0$, $k⩾3$ and $p=cn∕\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, we prove that if $c<\frac{ln3}{3}\cdot {\left(\frac{3}{2}\right)}^k-\frac{ln3}{2}-O\left({\left(\frac{\sqrt{3}}{2}\right)}^k\right)$then $H(n,k,p)$ admits a panchromatic 3-coloring with probability tending to 1 as $n\to \infty$, but if $k$ is large enough and $c>\frac{ln3}{3}\cdot {\left(\frac{3}{2}\right)}^k-\frac{ln3}{2}+O\left({\left(\frac{3}{4}\right)}^k\right)$then $H(n,k,p)$ does not admit a panchromatic 3-coloring with probability tending to 1 as $n\to \infty$.     

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.     

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

Hunting rabbits on the hypercube

We explore the Hunters and Rabbits game on the hypercube. In the process, we find the solution for all classes of graphs with an isoperimetric nesting property and find the exact hunter number of $Q^n$ to be $1+{\sum }_{i=0}^{n?2}\left(\genfrac{}{}{0ex}{}{i}{?i∕2?}\right)$. In addition, we extend results to the situation where we allow the rabbit to not move between shots.     

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

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

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

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

Improvements on Hippchen's conjecture

Let G be a k-connected graph on n vertices. Hippchen's Conjecture (2008) states that two longest paths in G share at least k vertices. Gutiérrez (2020) recently proved the conjecture when $k\le 4$ or $k\ge \frac{n?2}{3}$. We improve upon both results; namely, we show that two longest paths in G share at least k vertices when $k=5$ or $k\ge \frac{n+2}{5}$. This completely resolves two conjectures by Gutiérrez in the affirmative.