Перестановки строк и столбцов в матрицах

[nikov]

Верно ли, что для любого N существует такое K, что в любой булевой квадратной матрице порядка K можно так переставить строки и столбцы (независимо), что в ней найдется подматрица порядка N, все элементы которой одинаковы?

(мне это напоминает теорему Рамсея, но явную связь установить не получается)

[Хорхе]

Есть такая теорема -- теорема Рамсея для двудольных графов. Число цветов может быть любое. Свистите, если не нагуглите.

-- Пт фев 11, 2011 10:32:43 --

Кстати, есть даже и немного более сильный результат: для всяких $\varepsilon>0$ и $n>0$ найдется $N$ такое, что как только плотность ребер в двудольном графе на $N+N$ вершинах (или, если угодно, плотность единиц в бинарной матрице размером $N\times N$), больше $\varepsilon$, то в нем найдется полный двудольный подграф на $n+n$ ребрах.

Ну и для $k$-дольного тоже верно, perhaps unsurprisingly.

-- Пт фев 11, 2011 10:39:18 --

Впрочем, можете не гуглить, оно оказалось там, где и должно было быть: тут, раздел 5.1.

[nikov]

Большое спасибо, то что нужно!
Интересно, а что получится, если рассмотреть не матрицу, а 3-мерную (или N-мерную) таблицу из 0 и 1?

-- Сб фев 12, 2011 05:01:13 --

А как растет минимальное K с ростом N?

[Хорхе]

Как растет минимальное $K$, оценки в книжке и в интернете (по запросу ramsey bipartite) есть.

Для многомерных матриц тоже должно быть правильно. Я думаю, похожими методами можно вывести. Если не получится, пишите, придумаем что-нибудь.