Density of monochromatic infinite paths

MaRDI QIDQ1627204zbMATH OpenFDO

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

Publication date 22 November 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.00389, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p29

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

density of monochromatic subgraphsinfinite pathsRamsey theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Infinite graphs (05C63)

Abstract: For any subset $AsubseteqmathbbN$, we define its upper density to be $limsu{p}_{nightarrowinfty}|Acap1,dotsc,n|/n$. We prove that every $2$-edge-colouring of the complete graph on $mathbbN$ contains a monochromatic infinite path, whose vertex set has upper density at least $(9+sqrt17)/16approx0.82019$. This improves on results of ErdH{o}s and Galvin, and of DeBiasio and McKenney.

Review text

Summary: For any subset \(A \subseteq \mathbb{N}\), we define its upper density to be \(\limsup_{n\rightarrow\infty}|A \cap \{1,\ldots,n\}|/n\). We prove that every \(2\)-edge-colouring of the complete graph on \(\mathbb{N}\) contains a monochromatic infinite path, whose vertex set has upper density at least \((9+\sqrt{17})/16\approx 0.82019\). This improves on results of \textit{P. Erdős} and \textit{F. Galvin} [Discrete Math. 113, No. 1--3, 59--70 (1993; Zbl 0787.05071)], and of \textit{L. DeBiasio} and \textit{P. McKenney} [``Density of monochromatic infinite subgraphs, Combinatorica (to appear)].

Recommendations

• Upper density of monochromatic infinite paths
• Density of monochromatic infinite subgraphs
• Ramsey upper density of infinite graph factors
• Monochromatic infinite paths
• Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II

Cites work

• Density of monochromatic infinite subgraphs
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• Monochromatic infinite paths
• Monochromatic Paths in Graphs
• Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs
• Some Ramsey-type theorems
• Some Remarks on Ramsay's Theorem

Cited in

(10)

• Infinite monochromatic paths and a theorem of Erdős-Hajnal-Rado
• Density of monochromatic infinite subgraphs
• Monochromatic infinite paths
• The saturation number for the length of degree monotone paths
• Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs
• Upper density of monochromatic infinite paths
• Ramsey upper density of infinite graph factors
• Ramsey upper density of infinite graphs
• Ramsey upper density of infinite graphs
• Density of monochromatic infinite subgraphs. II

This page was built for publication: Density of monochromatic infinite paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1627204)