The Matching Ramsey Number of Hypergraphs, Revisited
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913979308179456 |
|---|---|
| author | Shaebani, Saeed Alishahi, Meysam |
| author_facet | Shaebani, Saeed Alishahi, Meysam |
| contents | Suppose that a hypergraph ${\mathcal H}$ and an arbitrary nonempty (finite or infinite) set of available colors are given. Each color $x$ is associated with a frequency $τ(x)$, where the set of all such frequencies is bounded. We define a new parameter called the {\it $τ$-matching chromatic number}, denoted by $χ_M(τ, {\mathcal H})$, as the least possible number of colors required to color the edges of ${\mathcal H}$ in such a way that the size of each nonempty monochromatic matching does not exceed the frequency of the corresponding color associated to its edges. The well-known and extensively well-studied chromatic number of general Kneser hypergraph $χ\left( {\rm KG}^r({\mathcal H}) \right)$ is a special case of $χ_M(τ, {\mathcal H})$ when all color frequencies are the fixed constant $r-1$.
In this paper, we establish sharp lower bounds for the parameter $χ_M(τ, {\mathcal H})$, utilizing the concepts of the alternation number and the equitable colorability defect. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2101_04701 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Matching Ramsey Number of Hypergraphs, Revisited Shaebani, Saeed Alishahi, Meysam Combinatorics 05C15 Suppose that a hypergraph ${\mathcal H}$ and an arbitrary nonempty (finite or infinite) set of available colors are given. Each color $x$ is associated with a frequency $τ(x)$, where the set of all such frequencies is bounded. We define a new parameter called the {\it $τ$-matching chromatic number}, denoted by $χ_M(τ, {\mathcal H})$, as the least possible number of colors required to color the edges of ${\mathcal H}$ in such a way that the size of each nonempty monochromatic matching does not exceed the frequency of the corresponding color associated to its edges. The well-known and extensively well-studied chromatic number of general Kneser hypergraph $χ\left( {\rm KG}^r({\mathcal H}) \right)$ is a special case of $χ_M(τ, {\mathcal H})$ when all color frequencies are the fixed constant $r-1$. In this paper, we establish sharp lower bounds for the parameter $χ_M(τ, {\mathcal H})$, utilizing the concepts of the alternation number and the equitable colorability defect. |
| title | The Matching Ramsey Number of Hypergraphs, Revisited |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2101.04701 |