Star-critical Ramsey numbers for large generalized fans and books

In this paper, we show that for any fixed integers $m\ge 2$ and $t\ge 2$, the star-critical Ramsey number $r_1(K_1+n{K}_t,K_{m+1})=(m?1)tn+t$ for all sufficiently large $n$. Furthermore, for any fixed integers $p\ge 2$ and $m\ge 2$, $r_1(K_p+n{K}_1,K_{m+1})=(m?1+o\left(1\right))n$ as $n\to \infty$.     

Bijections between generalized Catalan families of types A and C

Motivated by the relation ${\mathsf{N}}^m\left(C_n\right)=(mn+1){\mathsf{N}}^m\left(A_{n?1}\right)$, holding for the $m$-generalized Catalan numbers of type $A$ and $C$, the connection between dominant regions of the $m$-Shi arrangement of type $A_{n?1}$ and $C_n$ is investigated. More precisely, it is explicitly shown how $mn+1$ copies of the set of dominant regions of the $m$-Shi arrangement of type $A_{n?1}$, biject onto the set of type $C_n$ such regions. This is achieved by exploiting two different viewpoints of the representative alcove of each region: the Shi tableau and the abacus diagram. In the same line of thought, a bijection between $mn+1$ copies of the set of $m$-Dyck paths of height $n$ and the set of $N?E$ lattice paths inside an $n\times mn$ rectangle is provided.     

Enumeration formulas for standard Young tableaux of nearly hollow rectangular shapes

This paper considers the enumeration problem of a generalization of standard Young tableau (SYT) of truncated shape. Let $\lambda ?\mu |\left\{(i_0,j_0)\right\}$ be the SYT of shape $\lambda$ truncated by $\mu$ whose upper left cell is $(i_0,j_0)$, where $\lambda$ and $\mu$ are partitions of integers. The summation representation of the number of SYT of the truncated shape $(n+k+2,{(n+2)}^{m+1})?\left(n^m\right)|\left\{(2,2)\right\}$ is derived. Consequently, three closed formulas for SYT of hollow shapes are obtained, including the cases of (i). $m=n=1$, (ii). $k=0$, and (iii). $k=1,m=n$. Finally, an open problem is posed.     

Lonesum decomposable matrices

A lonesum matrix is a $(0,1)$-matrix that is uniquely determined by its row and column sum vectors. In this paper, we introduce lonesum decomposable matrices and study their properties. We provide a necessary and sufficient condition for a matrix $A$ to be lonesum decomposable, and give a generating function for the number $D_k(m,n)$ of $m\times n$ lonesum decomposable matrices of order $k$. Moreover, by using this generating function we prove some congruences for $D_k(m,n)$ modulo a prime.     

On some cycles in linearized Wenger graphs

Let ${\mathbb{F}}_q$ be the finite field of $q$ elements for prime power $q$ and let $p$ be the character of ${\mathbb{F}}_q$. For any positive integer $m$, the linearized Wenger graph $L_m\left(q\right)$ is defined as follows: it is a bipartite graph with the vertex partitions being two copies of the $(m+1)$-dimensional vector space ${\mathbb{F}}_q^{m+1}$, and two vertices $p=\left(p\left(1\right),\dots ,p(m+1)\right)$ and $l=\left[l\left(1\right),\dots ,l(m+1)\right]$ being adjacent if $p\left(i\right)+l\left(i\right)=p\left(1\right){\left(l\left(1\right)\right)}^{p^{i?2}}$, for all $i=2,3,\dots ,m+1$. In this paper, we show that for any positive integers $m$ and $k$ with $3\le k\le p^2$, $L_m\left(q\right)$ contains even cycles of length $2k$ which is an open problem put forward by Cao et al. (2015).     

Homomorphism complexes and k-cores

For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex Hom($G,K_m$) is at least $m?D\left(G\right)?2$, where $D\left(G\right)={max}_{H?G}\delta \left(H\right)$, for $\delta \left(H\right)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree $\Delta \left(G\right)$ was used in place of $D\left(G\right)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi \left(G\right)\le D\left(G\right)+1$, as $\chi \left(G\right)=min\{m:\text{Hom}(G,K_m)\ne ?\}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c∕n$ for a fixed constant $c>0$.     

Explicit min–max polynomials on the disc

Denote by ${\Pi }_{n+m?1}^2?\{{\sum }_{0\le i+j\le n+m?1}{c}_{i,j}{x}^i{y}^j:c_{i,j}\in \mathbb{R}\}$ the space of polynomials of two variables with real coefficients of total degree less than or equal to $n+m?1$. Let $b_0,b_1,\dots ,b_l\in \mathbb{R}$ be given. For $n,m\in \mathbb{N},n\ge l+1$ we look for the polynomial $b_0{x}^n{y}^m+b_1{x}^{n?1}{y}^{m+1}+?+b_l{x}^{n?l}{y}^{m+l}+q(x,y),q(x,y)\in {\Pi }_{n+m?1}^2$, which has least maximum norm on the disc and call such a polynomial a min–max polynomial. First we introduce the polynomial $2P_{n,m}(x,y)=x{G}_{n?1,m}(x,y)+y{G}_{n,m?1}(x,y)=2x^n{y}^m+q(x,y)$ and $q(x,y)\in {\Pi }_{n+m?1}^2$, where $G_{n,m}(x,y)?1/2^{n+m}(U_n\left(x\right)U_m\left(y\right)+U_{n?2}\left(x\right)U_{m?2}\left(y\right))$, and show that it is a min–max polynomial on the disc. Then we give a sufficient condition on the coefficients $b_j,j=0,\dots ,l,l$ fixed, such that for every $n,m\in \mathbb{N},n\ge l+1$, the linear combination ${\sum }_{\nu =0}^l{b}_{\nu }{P}_{n?\nu ,m+\nu }(x,y)$ is a min–max polynomial. In fact the more general case, when the coefficients $b_j$ and $l$ are allowed to depend on $n$ and $m$, is considered. So far, up to very special cases, min–max polynomials are known only for $x^n{y}^m$,$n,m\in {\mathbb{N}}_0$.