Odd-Ramsey numbers of complete bipartite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917797680906240 |
|---|---|
| author | Boyadzhiyska, Simona Das, Shagnik Lesgourgues, Thomas Petrova, Kalina |
| author_facet | Boyadzhiyska, Simona Das, Shagnik Lesgourgues, Thomas Petrova, Kalina |
| contents | In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs $\mathcal{H}$ in $K_n$, defined as the minimum number of colours needed to colour the edges of $K_n$ so that every copy of a graph $H\in \mathcal{H}$ intersects some colour class in an odd number of edges. In this paper, we focus on complete bipartite graphs. First, we completely resolve the problem when $\mathcal{H}$ is the family of all spanning complete bipartite graphs on $n$ vertices. We then focus on its subfamilies, that is, $\{K_{t,n-t}\colon t\in T\}$ for a fixed set of integers $T\subseteq [\lfloor n/2 \rfloor]$. We prove that the odd-Ramsey problem is equivalent to determining the maximum dimension of a linear binary code avoiding codewords of given weights, and leverage known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05887 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Odd-Ramsey numbers of complete bipartite graphs Boyadzhiyska, Simona Das, Shagnik Lesgourgues, Thomas Petrova, Kalina Combinatorics 05D10, 05C55, 94B05, 05C35, 05D40 In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs $\mathcal{H}$ in $K_n$, defined as the minimum number of colours needed to colour the edges of $K_n$ so that every copy of a graph $H\in \mathcal{H}$ intersects some colour class in an odd number of edges. In this paper, we focus on complete bipartite graphs. First, we completely resolve the problem when $\mathcal{H}$ is the family of all spanning complete bipartite graphs on $n$ vertices. We then focus on its subfamilies, that is, $\{K_{t,n-t}\colon t\in T\}$ for a fixed set of integers $T\subseteq [\lfloor n/2 \rfloor]$. We prove that the odd-Ramsey problem is equivalent to determining the maximum dimension of a linear binary code avoiding codewords of given weights, and leverage known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs. |
| title | Odd-Ramsey numbers of complete bipartite graphs |
| topic | Combinatorics 05D10, 05C55, 94B05, 05C35, 05D40 |
| url | https://arxiv.org/abs/2410.05887 |