Ramsey Numbers for Rectangles in Multicolour Colourings
The article considers a Ramsey-theoretic approach to the analysis of discrete two-dimensional structures in which regular subconfigurations inevitably emerge as the size grows. The starting point is the central idea of Ramsey theory that in a sufficiently large system «complete chaos» is impossible:...
Gespeichert in:
| Datum: | 2025 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2025
|
| Online Zugang: | http://mcm-math.kpnu.edu.ua/article/view/346325 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543294422515712 |
|---|---|
| author | Зеленський, Олексій Динич, Альона Брігідіна, Валерія Онищенко, Катерина |
| author_facet | Зеленський, Олексій Динич, Альона Брігідіна, Валерія Онищенко, Катерина |
| author_sort | Зеленський, Олексій |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2026-01-25T14:19:53Z |
| description | The article considers a Ramsey-theoretic approach to the analysis of discrete two-dimensional structures in which regular subconfigurations inevitably emerge as the size grows. The starting point is the central idea of Ramsey theory that in a sufficiently large system «complete chaos» is impossible: regardless of how the structure is constructed, an ordered substructure must appear. We study multicolour fillings of a rectangular grid a × b under the prohibition of a monochromatic axis-aligned rectangle, which is treated as a basic local pattern of order.
Threshold characteristics are introduced to describe the boundaries of existence of admissible configurations: parameter regions are identified where the forbidden pattern can still be avoided (i.e., counterexamples exist), and regions where its appearance is guaranteed for any colouring. For the two- and three-colour cases, we obtain estimates related to the area of the largest nontrivial counterexamples and determine the smallest rectangles (by area) that can no longer be counterexamples. Thus, the results specify critical scales beyond which local regularity becomes unavoidable.
The obtained estimates have practical relevance in problems where it is important to control the emergence of repeating local configurations in matrix data. In particular, they can be used for mathematical modelling and for designing assignment matrices in «time–channel» allocation schemes (rows correspond to time slots, columns to channels or resources, and colours to classes/states) in order to reduce unwanted repetitions and artificial correlations. Moreover, the proposed approach is suitable for generating controlled test arrays in pattern-detection tasks for two-dimensional data (event matrices, observation maps, images), where one needs a guaranteed absence of a specified type of regularity up to a given size threshold |
| first_indexed | 2026-02-08T08:00:56Z |
| format | Article |
| id | mcm-mathkpnueduua-article-346325 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Ukrainian |
| last_indexed | 2026-02-08T08:00:56Z |
| publishDate | 2025 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-3463252026-01-25T14:19:53Z Ramsey Numbers for Rectangles in Multicolour Colourings Рамсеївські числа для прямокутників у багатокольорових розфарбуваннях Зеленський, Олексій Динич, Альона Брігідіна, Валерія Онищенко, Катерина The article considers a Ramsey-theoretic approach to the analysis of discrete two-dimensional structures in which regular subconfigurations inevitably emerge as the size grows. The starting point is the central idea of Ramsey theory that in a sufficiently large system «complete chaos» is impossible: regardless of how the structure is constructed, an ordered substructure must appear. We study multicolour fillings of a rectangular grid a × b under the prohibition of a monochromatic axis-aligned rectangle, which is treated as a basic local pattern of order. Threshold characteristics are introduced to describe the boundaries of existence of admissible configurations: parameter regions are identified where the forbidden pattern can still be avoided (i.e., counterexamples exist), and regions where its appearance is guaranteed for any colouring. For the two- and three-colour cases, we obtain estimates related to the area of the largest nontrivial counterexamples and determine the smallest rectangles (by area) that can no longer be counterexamples. Thus, the results specify critical scales beyond which local regularity becomes unavoidable. The obtained estimates have practical relevance in problems where it is important to control the emergence of repeating local configurations in matrix data. In particular, they can be used for mathematical modelling and for designing assignment matrices in «time–channel» allocation schemes (rows correspond to time slots, columns to channels or resources, and colours to classes/states) in order to reduce unwanted repetitions and artificial correlations. Moreover, the proposed approach is suitable for generating controlled test arrays in pattern-detection tasks for two-dimensional data (event matrices, observation maps, images), where one needs a guaranteed absence of a specified type of regularity up to a given size threshold У статті розглянуто рамсеївський підхід до аналізу дискретних двовимірних структур, у яких за зростання розмірів неминуче виникають регулярні підконфігурації. Вихідною є ідея теорії Рамсея про те, що в достатньо великій системі «повний хаос» неможливий: незалежно від способу побудови обов’язково з’являється впорядкована підструктура. Досліджується багатокольорове заповнення прямокутної ґратки a × b із забороною однотонного осьово-орієнтованого прямокутника, який розглядається як базовий локальний шаблон упорядкування. Уведено порогові характеристики, що описують межі існування допустимих конфігурацій: встановлюються області параметрів, де заборонений шаблон ще можна уникати (існують контрприклади), та області, де його поява стає гарантованою для будь-якого розфарбування. Для дво- та трикольорових випадків отримано оцінки, пов’язані з площею максимальних нетривіальних контрприкладів, а також визначено мінімальні за площею прямокутники, які вже не можуть бути контрприкладами. Таким чином, результати задають критичні масштаби, після яких локальна регулярність проявляється неминуче. Одержані оцінки мають прикладний сенс у задачах, де важливо контролювати появу повторюваних локальних конфігурацій у матричних даних. Зокрема, вони можуть бути використані для математичного моделювання та побудови матриць призначень у схемах розподілу «час-канал» (рядки відповідають часовим слотам, стовпці – каналам або ресурсам, колір – класу/стану), щоб зменшувати небажані повтори та штучні кореляції. Крім того, запропонований підхід придатний для формування контрольованих тестових масивів у задачах виявлення шаблонів у двовимірних даних (матрицях подій, картах спостережень, зображеннях), де потрібна гарантована відсутність заданого типу регулярності до певного порога розмірів Кам'янець-Подільський національний університет імені Івана Огієнка 2025-12-11 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/346325 10.32626/2308-5878.2025-28.54-66 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2025: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 28; 54-66 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2025: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 28; 54-66 2308-5878 10.32626/2308-5878.2025-28 uk http://mcm-math.kpnu.edu.ua/article/view/346325/337794 Авторське право (c) 2026 Олексій Зеленський, Альона Динич, Валерія Брігідіна, Катерина Онищенко |
| spellingShingle | Зеленський, Олексій Динич, Альона Брігідіна, Валерія Онищенко, Катерина Ramsey Numbers for Rectangles in Multicolour Colourings |
| title | Ramsey Numbers for Rectangles in Multicolour Colourings |
| title_alt | Рамсеївські числа для прямокутників у багатокольорових розфарбуваннях |
| title_full | Ramsey Numbers for Rectangles in Multicolour Colourings |
| title_fullStr | Ramsey Numbers for Rectangles in Multicolour Colourings |
| title_full_unstemmed | Ramsey Numbers for Rectangles in Multicolour Colourings |
| title_short | Ramsey Numbers for Rectangles in Multicolour Colourings |
| title_sort | ramsey numbers for rectangles in multicolour colourings |
| url | http://mcm-math.kpnu.edu.ua/article/view/346325 |
| work_keys_str_mv | AT zelensʹkijoleksíj ramseynumbersforrectanglesinmulticolourcolourings AT diničalʹona ramseynumbersforrectanglesinmulticolourcolourings AT brígídínavaleríâ ramseynumbersforrectanglesinmulticolourcolourings AT oniŝenkokaterina ramseynumbersforrectanglesinmulticolourcolourings AT zelensʹkijoleksíj ramseívsʹkíčisladlâprâmokutnikívubagatokolʹorovihrozfarbuvannâh AT diničalʹona ramseívsʹkíčisladlâprâmokutnikívubagatokolʹorovihrozfarbuvannâh AT brígídínavaleríâ ramseívsʹkíčisladlâprâmokutnikívubagatokolʹorovihrozfarbuvannâh AT oniŝenkokaterina ramseívsʹkíčisladlâprâmokutnikívubagatokolʹorovihrozfarbuvannâh |