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

Erdős–Gallai stability theorem for linear forests

The Erd?s–Gallai Theorem states that every graph of average degree more than $l?2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd?s–Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=\left({?}_{i=1}^k{P}_{2a_i}\right)?\left({?}_{i=1}^l{P}_{2b_i+1}\right)$ be $k+l$ disjoint paths of order $2a_1,\dots ,2a_k,2b_1+1,\dots ,2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\ge 2$. If the minimum degree $\delta \left(G\right)\ge {\sum }_{i=1}^k{a}_i+{\sum }_{i=1}^l{b}_i?1$, then $F?G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.     

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

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

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.     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

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

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

Strengthening the Murty–Simon conjecture on diameter 2 critical graphs

A graph is diameter-2-critical if its diameter is 2 but the removal of any edge increases the diameter. A well-studied conjecture, known as the Murty–Simon conjecture, states that any diameter-2-critical graph of order $n$ has at most $?n^2∕4?$ edges, with equality if and only if $G$ is a balanced complete bipartite graph. Many partial results about this conjecture have been obtained, in particular it is known to hold for all sufficiently large graphs, for all triangle-free graphs, and for all graphs with a dominating edge. In this paper, we discuss ways in which this conjecture can be strengthened. Extending previous conjectures in this direction, we conjecture that, when we exclude the class of complete bipartite graphs and one particular graph, the maximum number of edges of a diameter-2-critical graph is at most $?{(n?1)}^2∕4?+1$. The family of extremal examples is conjectured to consist of certain twin-expansions of the 5-cycle (with the exception of a set of thirteen special small graphs). Our main result is a step towards our conjecture: we show that the Murty–Simon bound is not tight for non-bipartite diameter-2-critical graphs that have a dominating edge, as they have at most $?n^2∕4??2$ edges. Along the way, we give a shorter proof of the Murty–Simon conjecture for this class of graphs, and stronger bounds for more specific cases. We also characterize diameter-2-critical graphs of order $n$ with maximum degree $n?2$: they form an interesting family of graphs with a dominating edge and $2n?4$ edges.     

Analytic aspects of Delannoy numbers

The Delannoy numbers $d(n,k)$ count the number of lattice paths from $(0,0)$ to $(n?k,k)$ using steps $(1,0),(0,1)$ and $(1,1)$. We show that the zeros of all Delannoy polynomials $d_n\left(x\right)={\sum }_{k=0}^{n}d(n,k)x^k$ are in the open interval $(?3?2\sqrt{2},?3+2\sqrt{2})$ and are dense in the corresponding closed interval. We also show that the Delannoy numbers $d(n,k)$ are asymptotically normal (by central and local limit theorems).     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

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.     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

Compactness of sign-changing solutions to scalar curvature-type equations with bounded negative part

We consider the equation ${\mathrm{\Delta }}_{g}u+hu=|u{|}^{2^{?}?2}u$ in a closed Riemannian manifold $(M,g)$, where $h\in C^{0,\theta }(M)$, $\theta \in (0,1)$ and $2^{?}=\frac{2n}{n?2}$, $n:=\dim ?(M)\ge 3$. We obtain a sharp compactness result on the sets of sign-changing solutions whose negative part is a priori bounded. We obtain this result under the conditions that $n\ge 7$ and $h<\frac{n?2}{4(n?1)}{\text{Scal}}_g$ in M, where ${\text{Scal}}_g$ is the Scalar curvature of the manifold. We show that these conditions are optimal by constructing examples of blowing-up solutions, with arbitrarily large energy, in the case of the round sphere with a constant potential function h.