Minimum supports of functions on the Hamming graphs with spectral constraints

We study functions defined on the vertices of the Hamming graphs $H(n,q)$. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_i(n,q)$ for $0\le i\le n$. In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus \cdots \oplus U_j(n,q)$ for $0\le i\le j\le n$. For the case $i+j\le n$ and $q\ge 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $i+j>n$ and $q\ge 4$ we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for $i=j$, $i>\frac{n}{2}$ and $q\ge 5$. In particular, we characterize eigenfunctions from the eigenspace $U_i(n,q)$ with the minimum cardinality of the support for cases $i\le \frac{n}{2}$, $q\ge 3$ and $i>\frac{n}{2}$, $q\ge 5$.     

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

Explicit computation of some families of Hurwitz numbers

We compute the number of (weak) equivalence classes of branched covers from a surface of genus $g$ to the sphere, with 3 branching points, degree $2k$, and local degrees over the branching points of the form $(2,\dots ,2)$, $(2h+1,1,2,\dots ,2)$, $\pi ={\left(d_i\right)}_{i=1}^{\ell }$, for several values of $g$ and $h$. We obtain explicit formulae of arithmetic nature in terms of the local degrees $d_i$. Our proofs employ a combinatorial method based on Grothendieck’s dessins d’enfant.     

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

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

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

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

On the Chebotarëv theorem over finite fields

Let p be a prime number and let $V_p$ be the Vandermonde matrix with $(i,j)$-entry equal to ${\omega }^{ij}$ for $0\le i,j\le p-1$, where ω is a primitive pth root of unity in the complex field. The classical Chebotarëv theorem says that all square submatrices of $V_p$ have nonzero determinant. In this paper, we establish the Chebotarëv theorem over finite fields by imposing certain conditions.     

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.     

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.     

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

The survival probability of critical and subcritical branching processes in finite state space Markovian environment

Let ${\left(Z_n\right)}_{n\ge 0}$ be a branching process in a random environment defined by a Markov chain ${\left(X_n\right)}_{n\ge 0}$ with values in a finite state space $\mathbb{X}$. Let ${\mathbb{P}}_i$ be the probability law generated by the trajectories of ${\left(X_n\right)}_{n\ge 0}$ starting at $X_0=i\in \mathbb{X}.$ We study the asymptotic behaviour of the joint survival probability ${\mathbb{P}}_i\left(Z_n>0,X_n=j\right)$, $j\in \mathbb{X}$ as $n\to +\infty$ in the critical and strongly, intermediate and weakly subcritical cases.     

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.     

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