ARTICLE
TITLE

On the Staircases of Gyárfás

SUMMARY

In a 2011 paper, Gyárfás investigated a geometric Ramsey problem on convex, separated, balanced, geometric Kn,nK_{n,n}. This led to appealing extremal problem on square 0-1 matrices. Gyárfás conjectured that any 0-1 matrix of size n×nn\times n has a staircase of size n-1n-1.We introduce the non-symmetric version of Gyárfás' problem. We give upper bounds and in certain range matching lower bound on the corresponding extremal function. In the square/balanced case we improve the (4/5+?)n(4/5+\epsilon)n lower bound of Cai, Gyárfás et al. to 5n/6-7/125n/6-7/12. We settle the problem when instead of considering maximum staircases we deal with the sum of the size of the longest 00- and 11-staircases.

PAGES
pp. P2.17

 Articles related

Baptiste Louf, Fiona Skerman    

In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by Krivelevich [SIAM J. Disc. Math. 32 1 (2018)]. Here, we show that the problem... see more


Louis Esperet, Daniel Gonçalves, Arnaud Labourel    

For a family of geometric objects in the plane F={S1,…,Sn}\mathcal{F}=\{S_1,\ldots,S_n\}, define ?(F)\chi(\mathcal{F}) as the least integer l\ell such that the elements of F\mathcal{F} can be colored with l\ell colors, in such a way that any two intersec... see more


Petteri Kaski, Jukka Kohonen, Thomas Westerbäck    

We consider the problem of fast zeta and Möbius transforms in finite posets, particularly in lattices. It has previously been shown that for a certain family of lattices, zeta and Möbius transforms can be computed in O(e)O(e) elementary arithmetic operat... see more


Gohar Kyureghyan, Shuxing Li, Alexander Pott    

The intersection distribution of a polynomial ff over finite field Fq\mathbb{F}_q was recently proposed by Li and Pott [\emph{Finite Fields and Their Applications, 66 (2020)}], which concerns the collective behaviour of a collection of polynomials {f(x)+... see more


Andrés Eduardo Caicedo, Thomas A. C. Chartier, Péter Pál Pach    

For which values of nn is it possible to color the positive integers using precisely nn colors in such a way that for any aa, the numbers a,2a,…,naa,2a,\dots,na all receive different colors? The third-named author posed the question around 2008-2009. Par... see more