On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices

Let $g(k,t)$ be the minimum integer such that every plane graph with girth g at least $g(k,t)$, minimum degree $\delta =2$ and no $(k+1)$-paths consisting of vertices of degree 2, where $k\ge 1$, has a 3-vertex with at least t neighbors of degree 2, where $1\le t\le 3$.In 2015, Jendrol' and Maceková proved $g(1,1)\le 7$. Later on, Hudák et al. established $g(1,3)=10$, Jendrol', Maceková, Montassier, and Soták proved $g(1,1)\ge 7$, $g(1,2)=8$ and $g(2,2)\ge 11$, and we recently proved that $g(2,2)=11$ and $g(2,3)=14$.Thus $g(k,t)$ is already known for $k=1$ and all t. In this paper, we prove that $g(k,1)=3k+4$, $g(k,2)=3k+5$, and $g(k,3)=3k+8$ whenever $k\ge 2$.     

Largest regular multigraphs with three distinct eigenvalues

We deal with connected $k$-regular multigraphs of order $n$ that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given $k$. For $k=2,3,7$, the Moore graphs are largest. For $k\ne 2,3,7,57$, we show an upper bound $n\le k^2?k+1$, with equality if and only if there exists a finite projective plane of order $k?1$ that admits a polarity.     

Classifying (almost)-Belyi maps with five exceptional points

We classify all rational functions $f:{\mathbb{P}}^1\to {\mathbb{P}}^1$ whose branching pattern above $0,1,\infty$ satisfy a certain regularity condition with precisely $d=5$ exceptions. This work is motivated by solving second order linear differential equations, with $d=5$ true singularities, in terms of hypergeometric functions. A similar problem was solved for $d=4$ in Vidunas and Filipuk (2013).     

The existence of 2-balanced Mendelsohn triple systems

A Mendelsohn triple system MTS$(v,b)$ is a collection of $b$ cyclic triples (blocks) on a set of $v$ points. It is $j$-balanced for $j=1,2,3$ when any two points, ordered pairs, or cyclic triples (resp.) are contained in the same or almost the same number of blocks (difference at most one). A $(2,3)$-balanced Mendelsohn triple system is an MTS$(v,b)$ that is both 2-balanced and 3-balanced. Employing large sets of Mendelsohn triple systems and partitionable Mendelsohn candelabra systems, we completely determine the spectrum for which a 2-balanced Mendelsohn triple system exists. Meanwhile, we determine the existence spectrum for a $(2,3)$-balanced Mendelsohn triple system.     

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

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

Sobolev homeomorphisms are dense in volume preserving automorphisms

In this paper we prove a weak version of Lusin's theorem for the space of Sobolev-$(1,p)$ volume preserving homeomorphisms on closed and connected n-dimensional manifolds, $n\ge 3$, for $p<n?1$. We also prove that if $p>n$ this result is not true. More precisely, we obtain the density of Sobolev-$(1,p)$ homeomorphisms in the space of volume preserving automorphisms, for the weak topology. Furthermore, the regularization of an automorphism in a uniform ball centered at the identity can be done in a Sobolev-$(1,p)$ ball with the same radius centered at the identity.