On the staircases of Gyárfás

MaRDI QIDQ281615zbMATH OpenFDO

Authors János Csányi, Péter Hajnal, Gábor V. Nagy

Publication date 11 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03504, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p17

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

0-1 matricesRamsey theory

Mathematics Subject Classification ID

Ramsey theory (05D10)

Abstract: Gy'arf'as 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'arf'as conjectured that any $0$-$1$ matrix of size $nimesn$ has a staircase of size $n-1$. We introduce the non-symmetric version of Gy'arf'as' 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 Cai, Gy'arf'as et al. 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.

Review text

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.

Recommendations

• Noncrossing monochromatic subtrees and staircases in 0-1 matrices
• Grid Ramsey problem
• scientific article; zbMATH DE number 1214945
• An Extremal Problem on Sparse 0-1 Matrices
• Polynomial bounds on geometric Ramsey numbers of ladder graphs

Cites work

• Noncrossing monochromatic subtrees and staircases in 0-1 matrices
• Ramsey-type results for geometric graphs. I
• Ramsey-type results for geometric graphs. II

Cited in

(2)

• The pavements of the Cosmati
• Stairway to hell

This page was built for publication: On the staircases of Gyárfás

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281615)