20
$\begingroup$

I just ran across this delightful paper by an amazing triumvirate:

Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20. (Cambridge link) (PDF download link)

 EHTDefinition

They prove that $K_n$ has dimension $n-1$, $K_{n,n}$ has dimension $\le 4$, and the dimension of the $n$-cube $Q_n$ is $2$. And the Petersen graph has dimension $2$:
     Fig7

Surely there must have been advances on characterizing graphs according to this concept in the last ~half-century(!). Can anyone provide some updates the status on this notion?

Update. Here is a modern, metrically accurate drawing of the Petersen graph:
   Petersen's
   (Image from Wikipedia: Unit Distance Graph)

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This is a fantastic problem but also very, very hard! Thanks for the absolutely priceless picture of the Petersen graph... $\endgroup$
    – François G. Dorais
    Commented Aug 30, 2013 at 1:12
  • $\begingroup$ Another closely related concept is that of $d$-realizability: If a graph $G$ has some realization in $\mathbb{R}^k$, there is a realization in $\mathbb{R}^d$ with the same edge lengths. E.g., paths and trees are 1-realizable but triangles are not. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 31, 2013 at 0:31

2 Answers 2

Reset to default
22
$\begingroup$

There are several well-known and hard problems in discrete geometry that concern the dimension of a graph. For example, the unit distance problem asks for the maximum number of edges of a graph on $n$ vertices of dimension 2. Erdős conjectured in the 1940s that the answer is $n^{1+o(1)}$, but the best known bound is only $O(n^{4/3})$.

The chromatic number of the plane is another famous problem about graphs of dimension $2$. This question asks for the maximum chromatic number of any graph with dimension $2$. The answer is only known to be between $4$ and $7$, and it has been stuck that way for more than five decades. Shelah and Soifer speculate in a series of papers that the answer might depend on the axioms for set theory. This is indeed the case for some other distance graphs they construct. A related result from Paul O'Donnell's thesis is that there are graphs of dimension $2$, chromatic number $4$, and arbitrarily large girth.

It is unlikely that graphs of dimension $2$ will be characterized in the near future.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks, Jacob! I especially appreciate your assessment in your closing sentence. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 30, 2013 at 19:31
12
$\begingroup$

To supplement Jacob Fox's answer: A short survey on this topic is presented in The mathematical coloring book by Alexander Soifer, Springer, New York 2009. MR2458293 (2010a:05005).

Chapter 13 is Dimension of a graph, and begins with the results of the Erdős-Harary-Tutte paper. He then discusses a variant, that he calls "Euclidean dimension" of a graph, with numerous references. The results of Chapter 14, Embedding $4$-Chromatic Graphs in the Plane are also related and, in particular, O’Donnell's results are discussed. (And you want to keep reading past this chapter as well.)

If you are not familiar with this book, you will find it is written in a very unique, personal style, it surprises when one first sees it. The book describes not just mathematical results but also stories surrounding their discovery. You may enjoy it.

Improve this answer
$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .