1Bolyai Institute, University of Szeged 2Bolyai Institute, University of Szeged and Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences
The electronic journal of combinatorics, Tome 23 (2016) no. 2
In a 2011 paper, Gyárfás 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-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 Cai, Gyárfás 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.
Classification :
05D10
Mots-clés :
0-1 matrices, Ramsey theory
Affiliations des auteurs :
János Csányi
1
;
Peter Hajnal
2
;
Gábor V. Nagy
1
1
Bolyai Institute,
University of Szeged
2
Bolyai Institute,
University of Szeged
and
Alfréd Rényi Institute of Mathematics,
Hungarian Academy of Sciences
@article{10_37236_5697,
author = {J\'anos Cs\'anyi and Peter Hajnal and G\'abor V. Nagy},
title = {On the staircases of {Gy\'arf\'as}},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {2},
doi = {10.37236/5697},
zbl = {1335.05176},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5697/}
}
TY - JOUR
AU - János Csányi
AU - Peter Hajnal
AU - Gábor V. Nagy
TI - On the staircases of Gyárfás
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5697/
DO - 10.37236/5697
ID - 10_37236_5697
ER -
%0 Journal Article
%A János Csányi
%A Peter Hajnal
%A Gábor V. Nagy
%T On the staircases of Gyárfás
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5697/
%R 10.37236/5697
%F 10_37236_5697
János Csányi; Peter Hajnal; Gábor V. Nagy. On the staircases of Gyárfás. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5697
