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:...
Saved in:
| Date: | 2025 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2025
|
| Online Access: | http://mcm-math.kpnu.edu.ua/article/view/346325 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| Summary: | 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 |
|---|