Max-norm Ramsey theory

DOI10.1016/J.EJC.2024.103918arXiv2111.08949OpenAlexW4391460847WikidataQ128867906 ScholiaQ128867906MaRDI QIDQ6201895FDOQ6201895

Authors: Nóra Frankl, Andrey B. Kupavskii, Arsenii Sagdeev 

Publication date: 26 March 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Given a metric space $mathcalM$ that contains at least two points, the chromatic number $chileft(mathbb{R}_{infty}^n,mathcalMight)$ is defined as the minimum number of colours needed to colour all points of an $n-$dimensional space $mathbb{R}_{infty}^n$ with the max-norm such that no isometric copy of $mathcalM$ is monochromatic. The last two authors have recently shown that the value $chileft(mathbb{R}_{infty}^n,mathcalMight)$ grows exponentially for all finite $mathcalM$. In the present paper we refine this result by giving the exact value $ch{i}_{mathcalM}$ such that $chileft(mathbb{R}_{infty}^n,mathcalMight)=(ch{i}_{mathcalM}+o(1){)}^n$ for all 'one-dimensional' $mathcalM$ and for some of their Cartesian products. We also study this question for infinite $mathcalM$. In particular, we construct an infinite $mathcalM$ such that the chromatic number $chileft(mathbb{R}_{infty}^n,mathcalMight)$ tends to infinity as $nightarrowinfty$.

Full work available at URL: https://arxiv.org/abs/2111.08949

zbMATH Keywords

chromatic numberEuclidean Ramsey theorychromatic number of the planeNelson's problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Graph operations (line graphs, products, etc.) (05C76) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)

Cites Work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring Distance Graphs and Graphs of Diameters
• The Mathematical Coloring Book
• On the chromatic number of a space
• The realization of distances within sets in Euclidean space
• Euclidean Ramsey theorems. I
• Title not available (Why is that?)
• Regularity and Positional Games
• Title not available (Why is that?)
• The chromatic number of a space with the metric $ l_q$
• A decomposition theorem for partially ordered sets
• A new proof of the density Hales-Jewett theorem
• A density version of the Hales-Jewett theorem
• Covering space with convex bodies
• All trapezoids are Ramsey
• Title not available (Why is that?)
• Transitive sets in Euclidean Ramsey theory
• Sequences of integers with three missing separations
• A Partition Property of Simplices in Euclidean Space
• Recent trends in Euclidean Ramsey theory
• Permutation Groups in Euclidean Ramsey Theory
• Monochromatic equilateral triangles in the unit distance graph
• Fractional chromatic number and circular chromatic number for distance graphs with large clique size
• On the chromatic number of with an arbitrary norm
• All regular polytopes are Ramsey
• Title not available (Why is that?)
• Alternative proof of Sine's theorem on the size of a regular polygon in \(\mathbb{R}{}^ n\) with the \(\ell{}_ \infty\)-metric
• Covering and packing in \({\mathbb Z}^n\) and \({\mathbb R}^n\). I
• Covering and packing in \({\mathbb Z^n}\) and \({\mathbb R^n}\). II
• Title not available (Why is that?)
• Polychromatic Colorings on the Integers
• The structure of translational tilings in $\mathbb{Z}^d$
• Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings
• Cardinalities of \(k\)-distance sets in Minkowski spaces
• A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space
• Upper bounds for the chromatic numbers of Euclidean spaces with forbidden Ramsey sets
• Lines in Euclidean Ramsey theory
• All finite sets are Ramsey in the maximum norm
• On covering by translates of a set
• The chromatic number of the plane is at least 5: a new proof
• The chromatic number of the plane is at least 5
• Domination ratio of a family of integer distance digraphs with arbitrary degree
• Odd-distance and right-equidistant sets in the maximum and Manhattan metrics
• Periodicity and decidability of tilings of ℤ2
• Exponentially Ramsey sets
• A note on near-optimal coloring of shift hypergraphs
• Two-Colorings of Normed Spaces without Long Monochromatic Unit Arithmetic Progressions
• Undecidable translational tilings with only two tiles, or one nonabelian tile

This page was built for publication: Max-norm Ramsey theory

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