Max-norm Ramsey theory

DOI10.1016/J.EJC.2024.103918OpenAlexW4391460847WikidataQ128867906 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

Recommendations

• All finite sets are Ramsey in the maximum norm
• On the chromatic number of with an arbitrary norm
• The chromatic number of a space with the metric $ l_q$
• On the chromatic numbers corresponding to exponentially Ramsey sets
• On the chromatic number of metric spaces

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

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

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)