Ramsey numbers of uniform loose paths and cycles
| Autor: | Maryam Shahsiah, Gholamreza Omidi |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Mathematics::Combinatorics Conjecture 010102 general mathematics 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Combinatorics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Ramsey's theorem 0101 mathematics Mathematics |
| Zdroj: | Discrete Mathematics. 340:1426-1434 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2016.09.024 |
| Popis: | Recently, determining the Ramsey numbers of loose paths and cycles in uniform hypergraphs has received considerable attention. It has been shown that the $2$-color Ramsey number of a $k$-uniform loose cycle $\mathcal{C}^k_n$, $R(\mathcal{C}^k_n,\mathcal{C}^k_n)$, is asymptotically $\frac{1}{2}(2k-1)n$. Here we conjecture that for any $n\geq m\geq 3$ and $k\geq 3,$ $$R(\mathcal{P}^k_n,\mathcal{P}^k_m)=R(\mathcal{P}^k_n,\mathcal{C}^k_m)=R(\mathcal{C}^k_n,\mathcal{C}^k_m)+1=(k-1)n+\lfloor\frac{m+1}{2}\rfloor.$$ Recently the case $k=3$ is proved by the authors. In this paper, first we show that this conjecture is true for $k=3$ with a much shorter proof. Then, we show that for fixed $m\geq 3$ and $k\geq 4$ the conjecture is equivalent to (only) the last equality for any $2m\geq n\geq m\geq 3$. Consequently, the proof for $m=3$ follows. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect