Distance graphs with large chromatic numbers and small clique numbers (Q1761033): Difference between revisions

From MaRDI portal
Changed label, description and/or aliases in en, and other parts
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
aliases / en / 0aliases / en / 0
 
Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
description / endescription / en
 
scientific article; zbMATH DE number 6190643
Property / title
 
Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size (English)
Property / title: Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size (English) / rank
 
Normal rank
Property / zbMATH Open document ID
 
Property / zbMATH Open document ID: 1268.05070 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1070/SM2013v204n04ABEH004310 / rank
 
Normal rank
Property / published in
 
Property / published in: Sbornik: Mathematics / rank
 
Normal rank
Property / publication date
 
24 July 2013
Timestamp+2013-07-24T00:00:00Z
Timezone+00:00
Calendar⧼valueview-expert-timevalue-calendar-gregorian⧽
Precision1 day
Before0
After0
Property / publication date: 24 July 2013 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C12 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C80 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C35 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05D10 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6190643 / rank
 
Normal rank
Property / zbMATH Keywords
 
distance graph
Property / zbMATH Keywords: distance graph / rank
 
Normal rank
Property / zbMATH Keywords
 
random graph
Property / zbMATH Keywords: random graph / rank
 
Normal rank
Property / zbMATH Keywords
 
clique
Property / zbMATH Keywords: clique / rank
 
Normal rank
Property / zbMATH Keywords
 
cycle
Property / zbMATH Keywords: cycle / rank
 
Normal rank
Property / author
 
Property / author: E. E. Demekhin / rank
 
Normal rank
Property / author
 
Property / author: O. I. Rubanov / rank
 
Normal rank
Property / cites work
 
Property / cites work: The realization of distances within sets in Euclidean space / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the chromatic number of a space / rank
 
Normal rank
Property / cites work
 
Property / cites work: Borsuk's problem and the chromatic numbers of some metric spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: On distance graphs with large chromatic number but without large simplices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph Theory and Probability / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3117615 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Distance graphs with large chromatic number and without large cliques / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Ramsey Type Problems in Combinatorial Geometry / rank
 
Normal rank
Property / cites work
 
Property / cites work: Intersection theorems with geometric consequences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2798999 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5808059 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Die Kugel als Körper extremaler Korona / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the space chromatic number / rank
 
Normal rank
Property / cites work
 
Property / cites work: A 15-colouring of 3-space omitting distance one / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finite Euclidean Ramsey theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: An estimate for the chromatic number of the space $ \mathbb R^4$ / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5692722 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3208683 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4876684 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4939324 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4484690 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4410025 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Research Problems in Discrete Geometry / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4339095 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4002287 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Mathematical Coloring Book / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chromatic numbers of 3-dimensional distance graphs containing no tetrahedra / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Difference Between Consecutive Primes, II / rank
 
Normal rank
Property / cites work
 
Property / cites work: The problems of Borsuk and Grunbaum on lattice polytopes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chromatic numbers of real and rational spaces with real or rational forbidden distances / rank
 
Normal rank
Property / cites work
 
Property / cites work: Estimating the chromatic numbers of Euclidean space by convex minimization methods / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3893810 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4146667 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5616849 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5592263 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2784326 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2743189 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4040194 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3290146 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5504826 / rank
 
Normal rank

Latest revision as of 16:33, 6 July 2024

scientific article; zbMATH DE number 6190643
  • Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
Language Label Description Also known as
English
Distance graphs with large chromatic numbers and small clique numbers
scientific article; zbMATH DE number 6190643
  • Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size

Statements

Distance graphs with large chromatic numbers and small clique numbers (English)
0 references
Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size (English)
0 references
0 references
0 references
15 November 2012
0 references
24 July 2013
0 references
An \(n\)-dimensional distance graph is a graph whose vertex set is a subset of \({\mathbb R}^n\), vertices being adjacent if their Euclidean distance equals \(a\), where \(a>0\) is an arbitrary fixed number. It is known that there exist distance graphs with large chromatic number and small clique number. More precisely, for every \(k\geq 3\) there exist a constant \(\zeta_k > 0\), a function \(\delta_k = \delta_k(n)\) such that \(\delta_k = o(1)\) as \(n\rightarrow \infty\), and a sequence of \(n\)-dimensional distance graphs \(G_n\), such that \(\chi(G) \geq (\zeta_k + \delta_k(n))^n\) and \(\omega(G_n) < k\) hold. In the present paper, all previously known bounds on \(\zeta_k\) are substantially refined. In particular, the new results yield non-trivial bounds for \(k=3\) and \(k=4\) which failed to be obtained earlier. The main tool is a considerable strengthening of the related probabilistic method. Sketches of the proofs are provided.
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
Euclidean distance graph
0 references
chromatic number
0 references
clique number
0 references
probabilistic method
0 references
distance graph
0 references
random graph
0 references
clique
0 references
cycle
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references