On the staircases of Gyárfás (Q281615): Difference between revisions

Summary: \textit{A. Gyárfás} [``Ramsey and Turán-type problems for non-crossing subgraphs of bipartite geometric graphs'', Ann. Univ. Sci. Budap. Rolando Eőtvős, Sect. Math. 54, 47--56 (2011)] investigated a geometric Ramsey problem on convex, separated, balanced, geometric \(K_{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\times n\) has a staircase of size \(n\mathrm{-}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+\epsilon)n\) lower bound of \textit{S. Cai} et al. [J. Discrete Math. 2014, Article ID 731519, 5 p. (2014; Zbl 1295.05149)] to \(5n/6-7/12\). We settle the problem when instead of considering maximum staircases we deal with the sum of the size of the longest 0- and 1-staircases.