On the nonexistence of pseudo-generalized quadrangles

In this paper, we consider the question of when a strongly regular graph with parameters $((s+1)(st+1),s(t+1),s-1,t+1)$ can exist. A strongly regular graph with such parameters is called a pseudo-generalized quadrangle. A pseudo-generalized quadrangle can be derived from a generalized quadrangle, but there are other examples which do not arise in this manner. If the graph is derived from a generalized quadrangle then $t\le s^2$ and $s\le t^2$, while for pseudo-generalized quadrangles we still have the former bound but not the latter. Previously, Neumaier has proved a bound for $s$ which is cubic in $t$, but we improve this to one which is quadratic. The proof involves a careful analysis of cliques and cocliques in the graph. This improved bound eliminates many potential parameter sets which were otherwise feasible.     

The graph Ramsey number R(Fℓ,K6)

For a given pair of two graphs $(F,H)$, let $R(F,H)$ be the smallest positive integer $r$ such that for any graph $G$ of order $r$, either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. Baskoro, Broersma and Surahmat (2005) conjectured that $R(F_{\ell },K_n)=2\ell (n-1)+1$for $\ell \ge n\ge 3$, where $F_{\ell }$ is the join $K_1+\ell K_2$ of $K_1$ and $\ell K_2$. In this paper, we prove that this conjecture is true for the case $n=6$.     

Independence number of products of Kneser graphs

We study the independence number of a product of Kneser graph $K(n,k)$ with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for $\alpha (K(n,k)⊠K(n,k))$ is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of $K(n,2)\square K(n,2)$, which are asymptotically tending to $n^3∕3$ and $3n^3∕8$, respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the $\ell$-independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs $K(2k+1,k)$, which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the $s$-stable Kneser graphs $K{(ks+1,k)}_{s-stab}$, derive a formula for their $\ell$-independence number, and give the exact value of the independence number of the Cartesian square of $K{(ks+1,k)}_{s-stab}$.     

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.     

Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations

Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph $K_{2n}$, $n\ge 3$, which is properly colored with $2n?1$ colors, the edge set can be partitioned into $n$ edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every $2n\in \{2^s:s\ge 3\}\cup \{5?2^s,s\ge 1\}$ . Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of $K_{2n}$ constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine’s result also to all $2n\in \{2^{s}d:s\ge 1,d>3\text{odd}\}$.     

On the asymptotic growth of bipartite graceful permutations

We give exact growth rates for the number of bipartite graceful permutations of the symbols $\{0,1,\dots ,n?1\}$ that start with $a$ for $a\le 14$ (equivalently, $\alpha$-labelings of paths with $n$ vertices that have $a$ as a pendant label). In particular, when $a=14$ the growth is asymptotically like ${\lambda }^n$ for $\lambda \approx 3.461$. The number of graceful permutations of length $n$ grows at least this fast, improving on the best existing asymptotic lower bound of $2.37^n$. Combined with existing theory, this improves the known lower bounds on the number of Hamiltonian decompositions of the complete graph $K_{2n+1}$ and on the number of cyclic oriented triangular embeddings of $K_{12s+3}$ and $K_{12s+7}$. We also give the first exponential lower bound on the number of R-sequencings of ${\mathbb{Z}}_{2n+1}$.     

Solutions for conformally invariant fractional Laplacian equations with multi-bumps centered in lattices

In this paper, we consider the following nonlinear elliptic equation involving the fractional Laplacian with critical exponent:

${(?\mathrm{\Delta })}^{s}u=K(x)u^{\frac{N+2s}{N?2s}},u>0\mathrm{in}{\mathbb{R}}^N,$

where $s\in (0,1)$ and $N>2+2s$, $K>0$ is periodic in $(x_1,\dots ,x_k)$ with $1\le k<\frac{N?2s}{2}$. Under some natural conditions on K near a critical point, we prove the existence of multi-bump solutions where the centers of bumps can be placed in some lattices in ${\mathbb{R}}^k$, including infinite lattices. On the other hand, to obtain positive solution with infinite bumps such that the bumps locate in lattices in ${\mathbb{R}}^k$, the restriction on $1\le k<\frac{N?2s}{2}$ is in some sense optimal, since we can show that for $k\ge \frac{N?2s}{2}$, no such solutions exist.     

Exponential lower bounds on the generalized Erdős–Ginzburg–Ziv constant

For a finite abelian group $G$, the generalized Erdős–Ginzburg–Ziv constant ${\mathsf{s}}_k\left(G\right)$ is the smallest $m$ such that a sequence of $m$ elements in $G$ always contains a $k$-element subsequence which sums to zero. If $n=exp\left(G\right)$ is the exponent of $G$, the previously best known bounds for ${\mathsf{s}}_{kn}\left(C_n^r\right)$ were linear in $n$ and $r$ when $k\ge 2$. Via a probabilistic argument, we produce the exponential lower bound ${\mathsf{s}}_{2n}\left(C_n^r\right)>\frac{n}{2}{[1.25+o\left(1\right)]}^r$for $n>0$. For the general case, we show ${\mathsf{s}}_{kn}\left(C_n^r\right)>\frac{kn}{4}{\left(1+\frac{1}{ek+1}+o\left(1\right)\right)}^r.$     

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.     

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