Density of monochromatic infinite paths

Allan Lo; Nicolás Sanhueza-Matamala; Guanghui Wang

Density of monochromatic infinite paths

Allan Lo, Nicolás Sanhueza-Matamala, Guanghui Wang

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

136 Downloads (Pure)

Abstract

For any subset A⊆N, we define its upper density to be lim supn→∞|A∩{1,…,n}|/n. We prove that every 2-edge-colouring of the complete graph on N contains a monochromatic infinite path, whose vertex set has upper density at least (9+17−−√)/16≈0.82019. This improves on results of Erdos and Galvin, and of DeBiasio and McKenney.

Original language	English
Article number	P4.29
Journal	Electronic Journal of Combinatorics
Volume	25
Issue number	4
Publication status	Published - 2 Nov 2018

Keywords

Infinite paths
Ramsey theory
Density of monochromatic subgraphs

Access to Document

Lo_etal_Density_of_monochromatic_infinite_paths_Electric_Journal_of_Combinatorics
© Lo at al 2018 first published in Journal of Combinatorics: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p29/pdf checked on 6/12/2018
Final published version, 333 KBLicence: Creative Commons: Attribution-NoDerivs (CC BY-ND)

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p29Licence: Creative Commons: Attribution-NoDerivs (CC BY-ND)

A graph theoretical approach for combinatorial designs
Lo, A.
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils

Cite this

@article{b31d5290333449f9ac1b2e2f7887bf7b,

title = "Density of monochromatic infinite paths",

abstract = "For any subset A⊆N, we define its upper density to be lim supn→∞|A∩{1,…,n}|/n. We prove that every 2-edge-colouring of the complete graph on N contains a monochromatic infinite path, whose vertex set has upper density at least (9+17−−√)/16≈0.82019. This improves on results of Erdos and Galvin, and of DeBiasio and McKenney.",

keywords = "Infinite paths, Ramsey theory, Density of monochromatic subgraphs",

author = "Allan Lo and Nicol{\'a}s Sanhueza-Matamala and Guanghui Wang",

year = "2018",

month = nov,

day = "2",

language = "English",

volume = "25",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "4",

}

TY - JOUR

T1 - Density of monochromatic infinite paths

AU - Lo, Allan

AU - Sanhueza-Matamala, Nicolás

AU - Wang, Guanghui

PY - 2018/11/2

Y1 - 2018/11/2

N2 - For any subset A⊆N, we define its upper density to be lim supn→∞|A∩{1,…,n}|/n. We prove that every 2-edge-colouring of the complete graph on N contains a monochromatic infinite path, whose vertex set has upper density at least (9+17−−√)/16≈0.82019. This improves on results of Erdos and Galvin, and of DeBiasio and McKenney.

AB - For any subset A⊆N, we define its upper density to be lim supn→∞|A∩{1,…,n}|/n. We prove that every 2-edge-colouring of the complete graph on N contains a monochromatic infinite path, whose vertex set has upper density at least (9+17−−√)/16≈0.82019. This improves on results of Erdos and Galvin, and of DeBiasio and McKenney.

KW - Infinite paths

KW - Ramsey theory

KW - Density of monochromatic subgraphs

M3 - Article

SN - 1077-8926

VL - 25

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - P4.29

ER -

Density of monochromatic infinite paths

Abstract

Keywords

Access to Document

Fingerprint

Projects

A graph theoretical approach for combinatorial designs

Cite this