Large monochromatic components in expansive hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913580602884096 |
|---|---|
| author | Bal, Deepak DeBiasio, Louis |
| author_facet | Bal, Deepak DeBiasio, Louis |
| contents | A result of Gyárfás exactly determines the size of a largest monochromatic component in an arbitrary $r$-coloring of the complete $k$-uniform hypergraph $K_n^k$ when $k\geq 2$ and $r-1\leq k\leq r$. We prove a result which says that if one replaces $K_n^k$ in Gyárfás' theorem by any ``expansive'' $k$-uniform hypergraph on $n$ vertices (that is, a $k$-uniform hypergraph $H$ on $n$ vertices in which in which $e(V_1, \dots, V_k)>0$ for all disjoint sets $V_1, \dots, V_k\subseteq V(H)$ with $|V_i|>α$ for all $i\in [k]$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on $r$ and $α$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms.
Gyárfás' result is equivalent to the dual problem of determining the smallest maximum degree of an arbitrary $r$-partite $r$-uniform hypergraph with $n$ edges in which every set of $k$ edges has a common intersection. In this language, our result says that if one replaces the condition that every set of $k$ edges has a common intersection with the condition that for every collection of $k$ disjoint sets $E_1, \dots, E_k\subseteq E(H)$ with $|E_i|>α$ for all $i\in [k]$ there exists $e_i\in E_i$ for all $i\in [k]$ such that $e_1\cap \dots \cap e_k\neq \emptyset$, then the maximum degree of $H$ is essentially the same (within a small error term depending on $r$ and $α$). We prove our results in this dual setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06669 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Large monochromatic components in expansive hypergraphs Bal, Deepak DeBiasio, Louis Combinatorics A result of Gyárfás exactly determines the size of a largest monochromatic component in an arbitrary $r$-coloring of the complete $k$-uniform hypergraph $K_n^k$ when $k\geq 2$ and $r-1\leq k\leq r$. We prove a result which says that if one replaces $K_n^k$ in Gyárfás' theorem by any ``expansive'' $k$-uniform hypergraph on $n$ vertices (that is, a $k$-uniform hypergraph $H$ on $n$ vertices in which in which $e(V_1, \dots, V_k)>0$ for all disjoint sets $V_1, \dots, V_k\subseteq V(H)$ with $|V_i|>α$ for all $i\in [k]$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on $r$ and $α$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás' result is equivalent to the dual problem of determining the smallest maximum degree of an arbitrary $r$-partite $r$-uniform hypergraph with $n$ edges in which every set of $k$ edges has a common intersection. In this language, our result says that if one replaces the condition that every set of $k$ edges has a common intersection with the condition that for every collection of $k$ disjoint sets $E_1, \dots, E_k\subseteq E(H)$ with $|E_i|>α$ for all $i\in [k]$ there exists $e_i\in E_i$ for all $i\in [k]$ such that $e_1\cap \dots \cap e_k\neq \emptyset$, then the maximum degree of $H$ is essentially the same (within a small error term depending on $r$ and $α$). We prove our results in this dual setting. |
| title | Large monochromatic components in expansive hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2302.06669 |