Combinatorics (math.CO)

Abstract: The set-valued tableaux are combinatorial objects introduced by Buch for expressing the tableaux-sum formula of the stable Grothendieck polynomials. Not much is known about the set-valued tableaux compared to the usual case of the semi-standard tableaux. In this paper, we show the odd property for the number of set-valued tableaux.

Abstract: Recently, new combinatorial structures called disjoint partial difference families (DPDFs) and external partial difference families (EPDFs) were introduced, which simultaneously generalize partial difference sets, disjoint difference families and external difference families, and have applications in information security. So far, all known construction methods have used cyclotomy in finite fields. We present the first non-cyclotomic infinite families of DPDFs which are also EPDFs, in structures other than finite fields (in particular cyclic groups and non-abelian groups). As well as direct constructions, we present an approach to constructing DPDFs/EPDFs using relative difference sets (RDSs); as part of this, we demonstrate how the well-known RDS result of Bose extends to a very natural construction for DPDFs and EPDFs.

Abstract: In 1993, Fishburn and Graham established the following qualitative extension of the classical Erd\H{o}s-Szekeres theorem. If $N$ is sufficiently large with respect to $n$, then any $N\times N$ real matrix contains an $n\times n$ submatrix in which every row and every column is monotone. We prove that the smallest such $N$ is at most $2^{n^{4+o(1)}}$, greatly improving the previously best known double-exponential upper bound, and getting close to the best known lower bound $n^{n/2}$. In particular, we prove the following surprising sharp transition in the asymmetric setting. On one hand, every $8n^2\times 2^{n^{4+o(1)}}$ matrix contains an $n\times n$ submatrix, in which every row is mononote. On the other hand, there exist $n^{2}/6\times 2^{2^{n^{1-o(1)}}}$ matrices containing no such submatrix .