Two notions of unit distance graphs

DOI10.1016/J.JCTA.2014.02.006MaRDI QIDQ2451892zbMATH OpenOpenAlexFDO

Authors Noga Alon, Andrey B. Kupavskii

Publication date 26 May 2014

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

graph dimensiongraph representationunit distance graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A {em faithful (unit) distance graph} in $mathbb{R}^d$ is a graph whose set of vertices is a finite subset of the $d$-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly $1$. A {em (unit) distance graph} in $mathbb{R}^d$ is any subgraph of such a graph. In the first part of the paper we focus on the differences between these two classes of graphs. In particular, we show that for any fixed $d$ the number of faithful distance graphs in $mathbb{R}^d$ on $n$ labelled vertices is $2^{(1+o(1))dnlo{g}_{2}n}$, and give a short proof of the known fact that the number of distance graphs in $mathbb{R}^d$ on $n$ labelled vertices is $2^{(1-1/lfloord/2floor+o(1))n^2/2}$. We also study the behavior of several Ramsey-type quantities involving these graphs. % and high-girth graphs from these classes. In the second part of the paper we discuss the problem of determining the minimum possible number of edges of a graph which is not isomorphic to a faithful distance graph in $mathbb{R}^d$.

Recommendations

• Two notions of unit distance graphs
• A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
• Unit-distance graphs, graphs on the integer lattice and a Ramsey type result
• scientific article; zbMATH DE number 2145238
• scientific article; zbMATH DE number 866045

Cites work

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Distance graphs with large chromatic number and arbitrary girth
• scientific article; zbMATH DE number 3730165 (Why is no real title available?)
• New bounds for the distance Ramsey number
• Note on induced subgraphs of the unit distance graph \(E^ n\)
• On the dimension to represent a graph by a unit distance graph
• On the number of zero-patterns of a sequence of polynomials
• Short cycles in random regular graphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The chromatic number of random graphs

Cited in

(21)

• On the chromatic numbers of rational spaces
• Embedding Euclidean distance graphs in \(\mathbb{R}^n\) and \(\mathbb{Q}^n\)
• On the chromatic numbers corresponding to exponentially Ramsey sets
• Minimal graphs with respect to geometric distance realizability
• The minrank of random graphs over arbitrary fields
• Lower bounds for the chromatic numbers of distance graphs with large girth
• Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres
• Deadlock analysis and resolution for multi-robot systems
• scientific article; zbMATH DE number 2145238 (Why is no real title available?)
• On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces
• Two notions of unit distance graphs
• Embedding graphs in Euclidean space
• Embedding graphs in Euclidean space
• The chromatic number of space with forbidden regular simplex
• On a combinatorial application of ultrafilter theory: a new construction of triangle-free graphs with arbitrarily large chromatic number
• Geometric Graphs with Exponential Chromatic Number and Arbitrary Girth
• Total orders realizable as the distances between two sets of points
• The Möbius-Kantor graph is a faithful unit-distance graph
• Local certification of geometric graph classes
• On the dimension to represent a graph by a unit distance graph
• On threshold probabilities for the realization of a random graph by a geometric graph

This page was built for publication: Two notions of unit distance graphs

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