The power of many colours
A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of $K_n$ ? We consider how big a connected component we can guarantee in any r-edge colouring of $K_n$ if we allow ourselves to use up...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2024-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509424001208/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846129330166431744 |
|---|---|
| author | Noga Alon Matija Bucić Micha Christoph Michael Krivelevich |
| author_facet | Noga Alon Matija Bucić Micha Christoph Michael Krivelevich |
| author_sort | Noga Alon |
| collection | DOAJ |
| description | A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of
$K_n$
? We consider how big a connected component we can guarantee in any r-edge colouring of
$K_n$
if we allow ourselves to use up to s colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a k-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided n is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. |
| format | Article |
| id | doaj-art-8b8e454ca2d34487a4f1c6bb8d89932c |
| institution | Kabale University |
| issn | 2050-5094 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj-art-8b8e454ca2d34487a4f1c6bb8d89932c2024-12-10T06:02:35ZengCambridge University PressForum of Mathematics, Sigma2050-50942024-01-011210.1017/fms.2024.120The power of many coloursNoga Alon0Matija Bucić1https://orcid.org/0000-0002-1055-3309Micha Christoph2Michael Krivelevich3https://orcid.org/0000-0003-2357-4982Department of Mathematics, Princeton University, Princeton, USA; E-mail:School of Mathematics, Institute for Advanced Study and Department of Mathematics, Princeton University, Princeton, USADepartment of Mathematics, ETH Zürich, Zürich, Switzerland; E-mail:School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel; E-mail:A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of $K_n$ ? We consider how big a connected component we can guarantee in any r-edge colouring of $K_n$ if we allow ourselves to use up to s colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a k-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided n is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form.https://www.cambridge.org/core/product/identifier/S2050509424001208/type/journal_article05C5505C4005D40 |
| spellingShingle | Noga Alon Matija Bucić Micha Christoph Michael Krivelevich The power of many colours Forum of Mathematics, Sigma 05C55 05C40 05D40 |
| title | The power of many colours |
| title_full | The power of many colours |
| title_fullStr | The power of many colours |
| title_full_unstemmed | The power of many colours |
| title_short | The power of many colours |
| title_sort | power of many colours |
| topic | 05C55 05C40 05D40 |
| url | https://www.cambridge.org/core/product/identifier/S2050509424001208/type/journal_article |
| work_keys_str_mv | AT nogaalon thepowerofmanycolours AT matijabucic thepowerofmanycolours AT michachristoph thepowerofmanycolours AT michaelkrivelevich thepowerofmanycolours AT nogaalon powerofmanycolours AT matijabucic powerofmanycolours AT michachristoph powerofmanycolours AT michaelkrivelevich powerofmanycolours |