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

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.     

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

Properties of G-martingales with finite variation and the application to G-Sobolev spaces

As is known, if $B={\left(B_t\right)}_{t\in [0,T]}$ is a $G$-Brownian motion, a process of form ${\int }_0^t{\eta }_{s}d{〈B〉}_s?{\int }_0^{t}2G\left({\eta }_s\right)ds$, $\eta \in M_G^1(0,T)$, is a non-increasing $G$-martingale. In this paper, we shall show that a non-increasing $G$-martingale cannot be form of ${\int }_0^t{\eta }_{s}ds$ or ${\int }_0^t{\gamma }_{s}d{〈B〉}_s$, $\eta ,\gamma \in M_G^1(0,T)$, which implies that the decomposition for generalized $G$-Itô processes is unique: For arbitrary $\zeta \in H_G^1(0,T)$, $\eta \in M_G^1(0,T)$ and non-increasing $G$-martingales $K,L$, if ${\int }_0^t{\zeta }_{s}d{B}_s+{\int }_0^t{\eta }_{s}ds+K_t=L_t,t\in [0,T],$then we have $\eta \equiv 0$, $\zeta \equiv 0$ and$K_t=L_t$. As an application, we give a characterization to the $G$-Sobolev spaces introduced in Peng and Song (2015).     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.     

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

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).