Today I’d like to discuss a beautiful inequality in graph theory, namely the crossing number inequality. This inequality gives a useful bound on how far a given graph is from being planar, and has a number of applications, for instance to sum-product estimates. Its proof is also an excellent example of the amplification trick in action; here the main source of amplification is the freedom to pass to subobjects, which is a freedom which I didn’t touch upon in the previous post on amplification. The crossing number inequality (and its proof) is well known among graph theorists but perhaps not among the wider mathematical community, so I thought I would publicise it here.
In this post, when I talk about a graph, I mean an abstract collection of vertices V, together with some abstract edges E joining pairs of vertices together. We will assume that the graph is undirected (the edges do not have a preferred orientation), loop-free (an edge cannot begin and start at the same vertex), and multiplicity-free (any pair of vertices is joined by at most one edge). More formally, we can model all this by viewing E as a subset of , the set of 2-element subsets of V, and we view the graph G as an ordered pair G = (V,E). (The notation is set up so that
.)
Now one of the great features of graphs, as opposed to some other abstract maths concepts, is that they are easy to draw: the abstract vertices become dots on a plane, while the edges become line segments or curves connecting these dots. [To avoid some technicalities we do not allow these curves to pass through the dots, except if the curve is terminating at that dot.] Let us informally refer to such a concrete representation D of a graph G as a drawing of that graph. Clearly, any non-trivial graph is going to have an infinite number of possible drawings. In some of these drawings, a pair of edges might cross each other; in other drawings, all edges might be disjoint (except of course at the vertices, where edges with a common endpoint are obliged to meet). If G has a drawing D of the latter type, we say that the graph G is planar.
Given an abstract graph G, or a drawing thereof, it is not always obvious as to whether that graph is planar; just because the drawing that you currently possess of G contains crossings, does not necessarily mean that all drawings of G do. The wonderful little web game “Planarity” illustrates this point excellently. Nevertheless, there are definitely graphs which are not planar; in particular the complete graph on five vertices, and the complete bipartite graph
on two sets of three vertices, are non-planar.
There is in fact a famous theorem of Kuratowski that says that these two graphs are the only “source” of non-planarity, in the sense that any non-planar graph contains (a subdivision of) one of these graphs as a subgraph. (There is of course the even more famous four-colour theorem that asserts that every planar graphs is four-colourable, but this is not the topic of my post today.)
Intuitively, if we fix the number of vertices |V|, and increase the number of edges |E|, then the graph should become “increasingly non-planar”; conversely, if we keep the same number of edges |E| but spread them amongst a greater number of vertices |V|, then the graph should become “increasingly planar”. Is there a quantitative way to measure the “non-planarity” of a graph, and to formalise the above intuition as some sort of inequality?
It turns out that there is an elegant inequality that does precisely this, known as the crossing number inequality. It was first discovered by Ajtai-Chvátal-Newborn-Szemerédi and by Leighton (the latter being motivated by optimising VLSI designs). Nowadays it can be proven by two elegant amplifications of Euler’s formula, as we shall see.
If D is a drawing of a graph G, we define cr(D) to be the total number of crossings – where pairs of edges intersect at a point, for a reason other than sharing a common vertex. (If multiple edges intersect at the same point, each pair of edges counts once.) We then define the crossing number cr(G) of G to be the minimal value of cr(D) as D ranges over the drawings of G. Thus for instance cr(G)=0 if and only if G is planar. One can also verify that the two graphs and
have a crossing number of 1. This quantity cr(G) will be the measure of how non-planar our graph G is. The problem is to relate this quantity in terms of the number of vertices |V| and the number of edges |E|. We of course do not expect an exact identity relating these three quantities (two graphs with the same number of vertices and edges may have a different number of crossing numbers), so will settle for good upper and lower bounds on cr(G) in terms of |V| and |E|.
How big can the crossing number of a graph G = (V,E) be? A trivial upper bound is cr(G) = O( |E|^2 ), because if we place the vertices in general position (or on a circle) and draw the edges as line segments, then every pair of edges crosses at most once. But this bound does not seem very tight; we expect to be able to find drawings in which most pairs of edges in fact do not intersect.
Let’s turn our attention instead to lower bounds. We of course have the trivial lower bound ; can we do better? Let’s first be extremely unambitious and see when one can get the minimal possible improvement on this bound, namely
. In other words, we want to find some conditions on |V| and |E| which will force G to be non-planar. We can turn this around by taking contrapositives: if G is planar, what does this tell us about |V| and |E|?
Here, the natural tool is Euler’s formula |V|-|E|+|F|=2, valid for any planar drawing, where |F| is the number of faces (including the unbounded face). [This is the one place where we shall really use the topological structure of the plane; the rest of the argument is combinatorial. There are some minor issues if the graph is disconnected, or if there are vertices of degree one or zero, but these are easily dealt with.] What do we know about |F|? Well, every face is adjacent to at least three edges, whereas every edge is adjacent to exactly two faces. By double counting the edge-face incidences, we conclude that . Eliminating |F|, we conclude that
for all connected planar graphs with at least one cycle (and this bound is tight when the graph is triangular), which then implies
in general. Taking contrapositives, we conclude
whenever
. (*)
Now, let us amplify this inequality by exploiting the freedom to delete edges. Indeed, observe that if a graph G can be drawn with only cr(G) crossings, then we can delete one of the crossings by removing an edge associated to that crossing, and so we can remove all the crossings by deleting at most cr(G) edges, leaving at least |E|-cr(G) edges (and |V| vertices). Combining this with (*) we see that regardless of the number of crossings, we have
leading to the following amplification of (*):
. (**)
This is not the best bound, though, as one can already suspect by comparing (**) with the crude upper bound . We can amplify (**) further by exploiting a second freedom, namely the ability to delete vertices. One could try the same sort of trick as before, deleting vertices which are associated to a crossing, but this turns out to be very inefficient (because deleting vertices also deletes an unknown number of edges, many of which had nothing to do with the crossing). Indeed, it would seem that one would have to be fiendishly clever to find an efficient way to delete a lot of crossings by deleting only very few vertices.
However, there is an amazing (and unintuitive) principle in combinatorics which states that when there is no obvious “best” choice for some combinatorial object (such as a set of vertices to delete), then often trying a random choice will give a reasonable answer, if the notion of “random” is chosen carefully. (See this paper of Gowers for some further discussion of this principle.) The application of this principle is known as the probabilistic method, first introduced by Erdős.
Here is how it works in this current setting. Let be a parameter to be chosen later. We will randomly delete all but a fraction p of the vertices, by letting each vertex be deleted with an independent probability of 1-p (and thus surviving with a probability of p). Let V’ be the set of vertices that remain. Once one deletes vertices, one also has to delete the edges attached to these vertices; let E’ denote the surviving edges (i.e. the edges connected to vertices in V’). Let G’=(V’,E’) be the surviving graph (known as the subgraph of G induced by V’). Then from (**) we have
.
Now, how do we get from this back to the original graph G = (V,E)? The quantities |V’|, |E’|, and cr(G’) all fluctuate randomly, and are difficult to compute. However, their expectations are much easier to compute. Accordingly, we take expectations of both sides (this is an example of the first moment method). Using linearity of expectation, we have
These quantities are all relatively easy to compute. The easiest is . Each vertex in V has a probability p of ending up in V’, and thus contributing 1 to |V’|. Summing up (using linearity of expectation again), we obtain
.
The quantity is almost as easy to compute. Each edge e in E will have a probability
of ending up in E’, since both vertices have an independent probability of p of surviving. Summing up, we obtain
. (The events that each edge ends up in E’ are not quite independent, but the great thing about linearity of expectation is that it works even without assuming any independence.)
Finally, we turn to . Let us draw G in the optimal way, with exactly cr(G) crossings. Observe that each crossing involves two edges and four vertices. (If the two edges involved in a crossing share a common vertex as well, thus forming an
shape, one can reduce the number of crossings by 1 by swapping the two halves of the loop in the
shape. So with the optimal drawing, the edges in a crossing do not share any vertices in common.) Passing to G’, we see that the probability that the crossing survives in this drawing is only
. By one last application of linearity of expectation, the expected number of crossings of this diagram that survive for G’ is
. This particular diagram may not be the optimal one for G’, so we end up with an inequality
. Fortunately for us, this inequality goes in the right direction, and we get a useful inequality:
.
In terms of cr(G), we have
.
To finish the amplification, we need to optimise in p, subject of course to the restriction , since p is a probability. One can solve the optimisation problem exactly, but we will perform a cheaper computation by settling for a bound which is close to the optimal bound rather than exactly equal to it. A general principle is that optima are often obtained when two of the terms are roughly in balance. A bit of thought reveals that it might be particularly good to have
just barely smaller than
. (If it is a lot smaller, then p will be large, and we don’t get a good bound on the right. If instead
is a lot bigger, then we are likely to have a negative right-hand side.) For instance, we could choose p so that
; this is legal as long as
. Substituting this we obtain the crossing number inequality
whenever
. (***)
This is quite a strong amplification of (*) or (**) (except in the transition region in which |E| is comparable to |V|).
Is it sharp? We can compare it against the trivial bound , and we observe that the two bounds match up to constants when |E| is comparable to
. (Clearly, |E| cannot be larger than
.) So the crossing number inequality is sharp (up to constants) for dense graphs, such as the complete graph
on n vertices.
Are there any other cases where it is sharp? We can answer this by appealing to the symmetries of (***). By the nature of its proof, the inequality is basically symmetric under passage to random induced subgraphs, but this symmetry does not give any further examples, because random induced subgraphs of dense graphs again tend to be dense graphs (cf. the computation of and
above). But there is a second symmetry of (***) available, namely that of replication. If one takes k disjoint copies of a graph G = (V,E), one gets a new graph with k|V| vertices and k|E| edges, and a moment’s thought will reveal that the new graph has a crossing number of k cr(G). Thus replication is a symmetry of (***). Thus, (***) is also sharp up to constants for replicated dense graphs. It is not hard to see that these examples basically cover all possibilities of |V| and |E| for which
. Thus the crossing number inequality cannot be improved except for the constants. (The best constants known currently can be found in a recent paper of Pach, Radoicic, Tardos, and Tóth.)
[A general principle, by the way, is that one can roughly gauge the “strength” of an inequality by the number of independent symmetries (or approximate symmetries) it has. If for instance there is a three-parameter family of symmetries, then any example that demonstrates that sharpness of that inequality is immediately amplified to a three-parameter family of such examples (unless of course the example is fixed by a significant portion of these symmetries). The more examples that show an inequality is sharp, the more efficient it is – and the harder it is to prove, since one cannot afford to lose anything (other than perhaps some constants) in every one of the sharp example cases. This principle is of course consistent with my previous post on arbitraging a weak asymmetric inequality into a strong symmetric one.]
— Application: the Szemerédi-Trotter theorem —
It was noticed by Székely that the crossing number is powerful enough to give easy proofs of several difficult inequalities in combinatorial incidence geometry. For instance, the Szemerédi-Trotter theorem concerns the number of incidences between a finite collection of points P and lines L in the plane. For instance, the three lines and three points of a triangle form six incidences; the five lines and ten points of a pentagram form 20 incidences; and so forth.
One can ask the question: given |P| points and |L| lines, what is the maximum number of incidences I(P,L) one can form between these points and lines? (The minimum number is obviously 0, which is a boring answer.) The trivial bound is , but one can do better than this, because it is not possible for every point to lie on every line. Indeed, if we use nothing more than the axiom that every two points determine at most one line, combined with the Cauchy-Schwarz inequality, it is not hard to show (by double-counting the space of triples
such that
) that
. (****)
Dually, using the axiom that two lines intersect in at most one point, we obtain
.
(One can also deduce one inequality from the other by projective duality.)
Can one do better? The answer is yes, if we observe that a configuration of points and lines naturally determines a drawing of a graph, to which the crossing number can be applied. To see this, assume temporarily that every line in L is incident to at least two points in P. A line l in L which is incident to k points in P will thus contain k-1 line segments in P; k-1 is comparable to k. Since the sum of all the k is I(P,L) by definition, we see that there are roughly I(P,L) line segments of L connecting adjacent points in P; this is a diagram with |P| vertices and roughly |I(P,L)| edges. On the other hand, a crossing in this diagram can only occur when two lines in L intersect. Since two lines intersect in at most one point, the total number of crossings is O(|L|^2). Applying the crossing number inequality (***), we obtain
if I(P,L) is much larger than |P|
which leads to
.
We can then remove our temporary assumption that lines in L are incident to at least two points, by observing that lines that are incident to at most one point will only contribute O(|L|) incidences, leading to the Szemerédi-Trotter theorem
.
This bound is somewhat stronger than the previous bounds, and is in fact surprisingly sharp; a typical example that demonstrates this is when P is the lattice and L is the set of lines
with slope
and intercept
; here
and the number of incidences is roughly
.
The original proof of this theorem, by the way, proceeded by amplifying (****) using the method of cell decomposition; it is thus somewhat similar in spirit to Szekély’s proof, but was a bit more complicated technically. Wolff conjectured a continuous version of this theorem for fractal sets, sometimes called the Furstenberg set conjecture, and related to the Kakeya conjecture; a small amount of progress beyond the analogue of (****) is known, thanks to work of Katz and myself and of Bourgain, but we are still far from the best possible result here.
— Application: sum-product estimates —
One striking application of the Szemerédi-Trotter theorem (and by extension, the crossing number inequality) is to the arena of sum-product estimates in additive combinatorics, which is currently a very active area of research, especially in finite fields, due to its connections with some long-standing problems in analytic number theory, as well as to some computer science problems concerning randomness extraction and expander graphs. However, our focus here will be on the more classical setting of sum-product estimates in the real line .
Let A be a finite non-empty set of non-zero real numbers. We can form the sum set
and the product set
.
If A is in “general position”, it is not hard to see that and
both have cardinality comparable to
. However, in certain cases one can make one or the other sets significantly smaller. For instance, if A is an arithmetic progression
, then the sum set
has cardinality comparable to just |A|. Similarly, if A is a geometric progression
, then the product set
has cardinality comparable to |A|. But clearly A cannot be an arithmetic progression and a geometric progression at the same time (unless it is very short). So one might conjecture that at least one of the sum set and product set should be significantly larger than A. Informally, this is saying that no finite set of reals can behave much like a subring of
.
This intuition was made precise by Erdős and Szemerédi, who established the lower bound
for some small which they did not make explicit. They then conjectured that in fact c should be made arbitrary close to the optimal value of 1, and more precisely that
for large |A| and some absolute constant .
The Erdős-Szemerédi conjecture remains open, however the value of c has been improved; currently, the best bound is due to Solymosi, who showed that c can be arbitrarily close to 3/11. Solymosi’s argument is based on an earlier argument of Elekes, who obtained c=1/4 by a short and elegant argument based on the Szemerédi-Trotter theorem which we will now present. The basic connection between the two problems stems from the familiar formula y=mx+b for a line, which clearly encodes a multiplicative and additive structure. We already used this connection implicitly in the example that demonstrated that the Szemerédi-Trotter theorem was sharp. For Elekes’ argument, the challenge is to show that if and
are both small, then a suitable family of lines
associated to A will have a high number of incidences with some set of points associated to A, so that the Szemerédi-Trotter may then be profitably applied. It is not immediately obvious exactly how to do this, but Elekes settled upon the choice of letting
, and letting L be the space of lines y=mx+b with slope in
and intercept in A, thus
and
. One observes that each line in L is incident to |A| points in P, leading to
incidences. Applying the Szemerédi-Trotter theorem and doing the algebra one eventually concludes that
. (A more elementary proof of this inequality, not relying on the Szemerédi-Trotter theorem or crossing number bounds, and thus having the advantage on working on other archimedean fields such as
, was subsequently found by Solymosi, but the best bounds on the sum-product problem in
still rely very much on the Szemerédi-Trotter inequality.)
58 comments
Comments feed for this article
18 September, 2007 at 10:41 pm
Suresh
Another beautiful result by Szekely was on the related problem, “how many unit distance pairs exist in a set of n points in the plane”. The bound (n^{4/3}) had been proven twice before, but the first time with very ugly constants, and the second time with better constants using the cell decomposition method. Szekely’s proof was one of those ‘from the book’ proofs of this fact. And unlike the Hopcroft problem (line-point incidences), this bound is nowhere near tight; the lower bound is only slightly superlinear.
19 September, 2007 at 7:05 am
Ben Webster
I get “Formula does not parse” for every single displayed formula in the post.
19 September, 2007 at 7:31 am
Anonymous
me too(formula does not parse) using firefox
19 September, 2007 at 8:13 am
Terence Tao
Others have reported this problem sporadically (while others simultaneously see no difficulty); my theory is that there are multiple wordpress servers, and there is some lag in getting the LaTeX images propagated properly. So far, it seems that refreshing the page after some time solves the problem by itself.
19 September, 2007 at 8:19 am
Dan Fitch
Refreshing the page will usually make the markup re-calculate.
Neat proofs and explanations.
19 September, 2007 at 11:07 am
Anonymous
In case G is already planar isn’t cr(G) zero? But E^3/64V^2 is always positive, contradicting (***).
19 September, 2007 at 11:43 am
Terence Tao
Dear anonymous,
(***) is only valid when |E| is larger than 4|V|. In contrast, in order for a graph to be planar, |E| cannot exceed 3|V|-6 (see (*)).
One can view 3|V|-6 as a threshold. If the number of edges lies below that number, there may be no crossings. But once one exceeds that threshold, the crossings build up quite quickly, and in fact starts growing like the cube of the number of edges (keeping |V| fixed).
19 September, 2007 at 5:52 pm
Doug
Hi Terence,
There appears to be some type of hierarchy among graphs, maps, lattices and images.
1 – RE: E8
a – crystal graph [perhaps either a sagittal or coronal perspective, medicine]
b – map of the E8 root system [perhaps an axial perspective, medicine]
http://aimath.org/E8/
Using imaging programs similar to AstroMed, should one be able to construct a 3D image of E8 [calculate the missing coronal or sagittal perspective]?
AstoMed: “The goal of the Harvard IIC’s “Astronomical Medicine” (AM) project is to extend the state of the art of complex data understanding in two very different fields, astronomy and medical imaging, using a broad-based approach to data exploration and analysis.“ [modified Magnetic Resonance Imaging, MRI]
http://astromed.iic.harvard.edu/
2 – Nuclear Magnetic Resonance [NMR] in ‘FirstGlance in Jmol’ reveals helices in many different molecules. The helices may likely have ionic molecules with a solenoid like effect? Example, Citrate Synthase:
http://molvis.sdsc.edu/fgij/fg.htm?mol=2cts
The latter may have something in common with your phrase from the text of this post:
“… and by Leighton (the latter being motivated by optimising VLSI designs).”
19 September, 2007 at 6:21 pm
John Armstrong
Doug, a 3-D image wouldn’t be much help.
has 248 dimensions, and even that’s not enough. You’re thinking of embedding it as a shape in some even higher-dimensional space, like we usually think of a 2-dimensional sphere living in 3-dimensional space.
Even if you just mean the root system, that’s really living in 8 dimensions thus, the 8 in
. It’s actually very well understood, even without drawing pictures, though. And that picture of the root system that was in all the papers is more because it looks pretty than for actual mathematical use.
19 September, 2007 at 7:48 pm
Top Posts « WordPress.com
[…] The crossing number inequality Today I’d like to discuss a beautiful inequality in graph theory, namely the crossing number inequality. This […] […]
19 September, 2007 at 8:51 pm
Prashant V
Dear Terry,
How did the following arise:
?
Was it more of a “guess and check” process? Are there any ways to get more accurate bounds?
20 September, 2007 at 9:07 am
Terence Tao
Dear Prashant,
This result is proven in a paper of Pach and Toth:
http://www.ams.org/mathscinet-getitem?mr=1606052
On briefly skimming the article, it seems that one of the key new ideas is to consider multigraphs rather than just graphs.
20 September, 2007 at 10:19 am
Mayifu
Dear Terry,
Off Topic. Have you thought about N-representable problem of the two-particle reduced-density matrix of a many-particle wave function?
21 September, 2007 at 2:09 am
Yoran
Dear Terence,
This is a great article! I’m a undergraduate Computer Science student and I had a course on graph theory last year. I find that subject very interesting. I knew about Euler’s formula, and Kuratowski as well, but I find this inequality very interesting. I think you explain it very well, and I never expected a Fields medal winner to write about something even an undergraduate can understand (I mean this in a positive way of course)!
21 September, 2007 at 2:22 am
Adam
I think a more exciting off-topic would be about incompatibilities
between various physical theories, e.g., quantum entangment
vs. special relativity or the Higgs’ particle controversy. However,
let me mention one topic which mathematicians are trying to deal
with. It is related to one of Terry’s previous posts.
Consider one of the Clay Institute problems: the incompressible
Navier-Stokes equations. From basic thermodynamics, pressure
is a function of density and temperature, e.g., in the ideal gas
law: p=kT\rho. However, \rho=const., therefore the gradient of
the pressure is really the gradient of the temperature. Question:
Does it make sense to use this equations in the health sciences?
In fact, as a rule, an equation of state is used to close the system
of compressible Euler equations.
21 September, 2007 at 1:49 pm
Doug
Hi John Armstrong,
I also posted at your blog in the post ‘Newton Fractals’.
Were dimensions always spatial I would readily agree with you.
Mathematical game theory has demonstrated that dimensions or degrees of freedom may also be strategic.
FUNDAMENTALS OF MRI: Part I, William G Bradley, MD, PhD, FACR
“MRI is based on a safe interaction between radio waves and hydrogen nuclei in the body in the presence of a strong magnetic field.”
“… volume element or “voxel” of tissue are translated by the computer into a two dimensional image composed of picture elements or “pixels”. ”
“… displays the body in thin tomographic slices …” [which can also mathematically be complied into a 3D image].
http://www.e-radiography.net/mrict/fund%20mr1/MRI%20fund1.htm
I suspect that significantly more than 248 hydrogen atoms are processed per tomographic slice as nodes [or vertices]. The total number may even exceed that of Monster dimensions for all slices.
I do not know if a 3D of E8 would be of use, but I suspect that it may. There may be a 3D with a time-D is nested or embedded within another 3D with time-D or there may exist 4-strategic-D [such as mass, temperature, pressure, vibration, etc] beyond the usual 3-spatial-D and time-D.
If the E8 crystal graph is identical for coronal and sagittal views, then combining them with the E8 root map may resemble a 3D torus?
21 September, 2007 at 3:51 pm
nimbusgear
Dear Terence,
Fabulous post, I was wondering what you might draw from the connection between graphs and knot theory.. From what i’ve read of knot theory, any given knot can be reduced to an ‘unknot’ by moving that knot into higher dimensions.
Regarding planarity in graphs however, what i draw from is that there is the simplest form of non-planarity.. the equivalent of an ‘unknot’, in the K5 and K3,3 forms.
That is, higher dimensional quantized geometry projected down to two dimensions results in an unknot (the planar ‘parts’) and harmonics of the non-planar K5 and K3,3 forms.
If this is a correct supposition on my part, i’d like to conjecture that as the dimensionless physical constants can be seen as ratios of one another, these ratios are geometric, and take the shape of a graph when plotted. Further, that these ratios may be the result of two or more crossing points of higher dimensional curves perhaps, projected down to 3d.
21 September, 2007 at 4:55 pm
John Armstrong
But Doug, the dimensions of
are spatial. And the dimensions in which the root system lives are spatial as well.
I may not specialize in Lie theory, but my series of posts on the Atlas Project (which followed that news story back in March) should confirm that I know what I’m talking about.
Yes, “degrees of freedom” have other interpretations, but you’re talking about drawing a picture, which means spatial interpretations. The dimensions in the pixel example you cite are greyscale values. Then a “picture” of
would be a collection of 248 points, each a different shade of grey. It doesn’t trigger human spatial intuition the way a pictorial representation is supposed to.
22 September, 2007 at 10:15 am
Terence Tao
Dear nimbusgear,
There are certainly analogies between the topology of graphs and of knots; knots, for instance, also have crossing number as an important invariant. And any graph can be made non-crossing in three dimensions, by assigning each vertex to a random location in space and using line segments to draw the edges (the point is that in three dimensions, any two randomly chosen line segments will be disjoint with probability 1). I am not aware though of any work which lets one understand the two-dimensional crossing number of a graph in terms of a higher-dimensional representation of that graph.
I am not an expert in knot theory, but I gather that nowadays one analyses knots by placing additional structures on top of the three-dimensional ambient space (such as a vector bundle or a quantum field theory) rather than lifting that ambient space (or the knot itself) into a higher-dimensional one. It may be one day that something similar happens for graphs, but I do not know of results in this direction.
22 September, 2007 at 5:21 pm
John Armstrong
Dr. Tao: Actually, there’s a growing trend to study knots from the purely combinatorial viewpoint, as with the Jones polynomial. And there’s one enterprising young mathematician I know of who used his dissertation to start the (possibly overly-)ambitious program of recasting all the old knot invariants as monoidal functors on suitable categories of tangles. Fascinating stuff, but he’s having a devil of a time getting hired anywhere.
24 September, 2007 at 12:27 pm
Doug
Hi Terence,
While doing more reading on MRI, I found this dissertation chapter
‘Stationarity and Ergodicity’
http://www.cs.utah.edu/~suyash/Dissertation_html/node25.html
in
Suyash P Awate, ‘Adaptive Nonparametric Markov Models and Information-Theoretic Methods for Image Restoration and Segmentation’, 2007-02-21.
http://www.cs.utah.edu/~suyash/Dissertation_html/Dissertation.html
I suspected that imaging was related to graphs and mapping, but was surprised by also having an ergodicity relation.
Hi John,
RE: your comment September 21st, 2007 at 4:55 pm
1 – I am not questioning your knowledge of E8 as currently understood by those who are expert on Lie theory..
I am questioning the current understanding that the supposedly spatial dimensions of E8 are necessarily spatial.
I think that Werner Heisenberg allows me to do this because of uncertainty.
I do understand that this idea applies specifically to position and momentum.
I may be over generalizing uncertainty when applied to types of dimensions.
If I am incorrect, then someone with better rigorous skills than my own, should be able to demonstrate this by contradiction.
Reasoning [correct any of my misconceptions]:
a – Monstrous Moonshine [MM] supposedly has 24-complex, 1-string, 1-time dimensions [D].
The 24-complex dimensions may be spatial or not?
b – M-theory has 1-time, 3-real-spatial, 6-compact, 1-[circle or line coupling] dimensions.
What if:
– The 6-compact consist of 3-real and 3-imaginary or perhaps simply 3-complex D.
– The 3-real-spatial may also actually be 3-complex D due to the work of Caspar Wessel [surveyor] and Charles Proteus Steinmetz [electrical engineer].
– The Earth and other celestial objects have an unseen but detectable 3D magnetosphere, perhaps due to imaginary numbers, plus the real 3D surface which is visible due to light electromagnetism.
– Thus there may be a nesting or embedding of 3-complex within 3-complex D.
– The coupling dimension may be equivalent to the string dimension.
– Thus M-theory may be of moonshine form: 6-complex, 1-string, 1-time dimension, total 8 D.
Could this be a version of E8?
I do not know the answer.
c – Perhaps MM is an eightfold nesting of 3-complex-D with 1 string-D, 1-time-D?
Perhaps MM is a threefold nesting of E8 with additional 1 string-D, 1-time-D?
2 – I suspect that you may be underestimating the power of mathematics as applied to greyscale imaging.
Quotes from Mark Dow, Research Assistant
Brain Development Lab, University of Oregon
“Space is a MS Windows application for the display, navigation, rendering, editing, and measurement of 3-D data sets.”
“While the program was developed for use with MRI data sets, no operations or tools are specific to MRI modalities.“
“Space Volume (.vol) native format, 8 bit grayscale, 8 bit indexed, 24 bit RGB color”
http://lcni.uoregon.edu/~mark/Space_software/Space_program/Space_program_description.htm
in
http://lcni.uoregon.edu/~mark/
3 – Additional reading suggest that I should have used the term ‘3D projection’
E8 (mathematics)
a – section ‘Applications’
“E8 is the U-duality group of supergravity on an eight-torus (in its split form).”
b – section ‘E8 root system’
Picture – Zome Model of the E8 Root System.
http://en.wikipedia.org/wiki/E8_(mathematics)
The zome structure pictured is more spherical than I visualized .
It may be a horn or spindle torus?
The E8 crystal graph suggested a much less rounded torus to me.
24 September, 2007 at 4:51 pm
John Armstrong
Uncertainty is not just about dimensions. It’s about when certain variables relate to each other in certain ways, like positions and momenta, or like time and energy. There’s a lot of extra structure here that just isn’t present in
.
“Monstrous Moonshine” is a conjecture. Are you thinking of the “Moonshine Module”, defined by Frankel et. al.? In that case, it was not originally related to string theory, so invoking strings here is completely spurious. The moonshine module is just a representation of a very large, but finite (not continuous) group.
is related, but very obliquely.
This is a module, which is based on a vector space, which is just a big, flat, 24-dimensional version of a plane. No visualization necessary.
M-theory has nothing. M-theory hasn’t been defined, much less rigorously laid out.
Still, in this context “spatial” and “temporal” have very specific meanings for the geometry. It’s not at all about interpretation or rendering.
No.
enters string theory in another way entirely.
Again, the module is just a vector space.
Yes, I understand that that’s what you were describing. But you still miss my point. We have a 248-dimensional manifold that may need a 500-dimensional space to be embedded smoothly in. We lose so much information projecting down to anything we can possibly visualize that it hardly matters if we use two or three dimensions to do it. And then invoking all these other concepts that you have only the haziest understanding of merely confuses the issue.
Look, I’m far from some sort of mathematical elitist that wants to keep these ideas the province of some sanctified priesthood, but the hallmark of the field is specifically-defined terms used in very specific ways. You can’t just take whatever words sound familiar and throw them together. If you do, you end up with The Tao of Physics (no relation to our host) or Transgressing the Boundaries: Towards a Transformative Hermeneutics of Quantum Gravity .
So yes, we can give all sorts of 3-dimensional projections of the manifold underlying
, and we can even do it without using any of the fancy technology you suggest. But none of them really help us in any way understand what
is.
25 September, 2007 at 7:00 am
Adam
The book “Transgressing the boundaries: …” has an interesting
and not well known piece of information, that Godel constructed
“an Einstein space-time admitting closed timelike curves: that is,
a universe in which it is possible to travel into one’s own past!”.
However, that laws of physics allow for time travel after the Big
Bang is a consequence of 19th century variational termodynamics
(exercise). A before the Big Bang version of this theory was used
by Perelman, who wrote that he knows it from string theory,
“where it describes the low energy effective action”, and the
functional is defined on “dilaton fields.” It has to be before, to
be compatible with the Higgs field electroweak unification, e.g.,
E. Witten, From superconductors and four-manifolds to weak
interactions, Bull. Amer. Math. Soc. 44 (2007), 361-391. See:
(4.4) and the modification into (4.9) after the Big Bang.
25 September, 2007 at 9:01 am
yury
Dear Terence,
do you know if there’s an upper bound on cr(G) if it’s known that G could be embedded into a torus? a surface of genus g? This case seems to fall somewhere between the planar case and the |E|>4|V| case.
25 September, 2007 at 10:23 am
Doug
Hi John,
I doubt that I have the ability to ever fully understand your point.
We appear to have different informational databases.
Example:
“Richard E. Borcherds will receive a medal for his work in the fields of algebra and geometry, in particular for his proof of the so-called Moonshine conjecture.”
“In 1989, Borcherds was able to cast some more light on the mathematical background of this topic and to produce a proof for the conjecture.”
http://www.icm2002.org.cn/general/prize/medal/1998.htm
Additional reading [only 2 listed each category:
Books
1 – Terry Gannon, Moonshine beyond the Monster: The Bridge Connecting Algebra, Modular Forms and Physics (Cambridge Monographs on Mathematical Physics)
2 – Mark Ronan, Symmetry and the Monster: The Story of One of the Greatest Quests of Mathematics
PDF
1 – see R.I. Ivanov and M.P. Tuite, Rational Generalised Moonshine from Abelian Orbifoldings of the Moonshine Module, Nucl.Phys. B635 435-472 (2002), http://arxiv.org/abs/math.QA/0106027.
from Generalised Monstrous Moonshine and Genus Two Conformal Field Theory [more pdf listed]
http://www.maths-physics.nuigalway.ie/users/Tuite/generalised_monstrous_moonshine.htm
2 – Yang-Hui He. Dept. of Physics and Math/Physics RG, Univ. of Pennsylvannia. Modular Matrix Models & Monstrous Moonshine: hep-th/0306092
or
25 September, 2007 at 12:26 pm
Adam
This is getting interesting. The simplicity of a group implies it is not
really an after Big Bang physical object. If ideas from string theory
were used to prove the Moonshine conjecture, then from
a philosophical perspective, does string theory tell us something
about the relationship between structures existing before the Big
Bang, and current physical reality? Maybe some kind of “homeopathic
imprint”?
25 September, 2007 at 3:00 pm
nimbusgear
I’ve been following your guy’s dialog, and would like to note that if you’re looking for big bang components, why not take a look at the fundamentals of quantization in the mathematical domain?
I speak of the various bases, operating on perhaps curves, perhaps other forms, but revealing a stage by stage quantization in terms of numeric value.
All forms at that level have fully defined symmetries, and are incredibly easy to grasp at in terms of quantization, harmonics, and modulations.
Looking to visualize the resonation of strings in the infinite scale infinite variation dimension, with a mathematical basis, it’s an easy go i’d highly suggest. ‘Just’ look at each symmetric combinational element (1 and 8 in base 9) as infinite length string moving in opposite directions operating on the base (9 in this case).
like so:
my apologies if this is too basic of a metaphor, the exponential version of this symmetric alignment in bases is more group theory:
http://mathworld.wolfram.com/ModuloMultiplicationGroup.html
Which brings me to a question for you guys..
Given the multitude of possible dimensions, even theoretical wackyness like basic physical constants changing in different origination conditions.. are we being limited in our ability to comprehend metaphor and properly form mathematical precision concepts, simply because of our physical universes’ properties?
Like, are we in any way limited by the neurological physicality of our existence in perceiving ‘really easy, obvious’ things?
25 September, 2007 at 5:50 pm
Terence Tao
Dear Yuri: It is not difficult to adapt the crossing number inequality to surfaces of higher genus g; one simply replaces Euler’s formula |V|-|E|+|F|=2 with the more general |V|-|E|+|F|=2-2g. One gets essentially the same inequality at the end (with some changes in constants) as long as |E| > 4 g (say). If instead |E| = O(g) then one basically has no non-trivial lower bound on the crossing number.
Dear all: the conversation here may be interesting, but it is now veering significantly off topic, being more physics and metaphysics than mathematics. Perhaps one of the participants would like to start a blog posting elsewhere dedicated to these topics, and link back here?
26 September, 2007 at 2:16 am
Adam
I don’t think we are as limited in our ability to comprehend metaphor
as it seems. To properly form precision concepts, we need a better
collaborative effort between hard sciences. E.g., it would be nice to
see mathematicians spend more time checking compatibilities between
various intuitive physical theories, as often this requires soft “analysis”
“threading a needle” thinking (to me, hard “analysis” is putting
together big structures, e.g., the textbook one line argument in
which Yukawa predicted the mass of the pi meson mediating the
strong nuclear force, using just the uncertainty principle and E=mc^2).
Instead, they often spend time dueling in joint works, which can last
many rounds (e.g., the longest I went through was 5).
As for our perceiving `really easy, obvious’ things, I also don’t think
we are that limited by our neurological physicality. E.g., the Aborigines
had the philosophy of living in harmony with the vibrations of the Earth.
A somewhat similar idea was later used in Lovelock’s Gaia theory (e.g.,
Gaia: A New Look at Life on Earth, Oxford University Press , 2000),
an exceptionally deep and logical explanation of processes that go
on in the atmosphere and the oceans. The author, however, keeps
mum on what goes on in the core, and doesn’t use the variational
termodynamics assumption of interacting complexes, which would
hint at a modern philosophy more compatible with Greek myths.
I suggest we move the off-topics discussions to:
https://terrytao.wordpress.com/2007/09/21/another-advice-page-and-an-open-thread/
26 September, 2007 at 6:17 am
yury
Dear Terence: I was actually wondering about the upper bound. That is, if we know that a graph can be embedded in a torus, is it true that it can also be drawn on a plane without too many intersections?
26 September, 2007 at 9:09 am
Terence Tao
That’s an interesting problem. If one takes the periodic lattice
in the torus
and connects all adjacent vertices, one gets a graph embedded in the torus with
vertices and
edges, and no crossings. If one naively tries to draw this graph in the plane it seems that one needs roughly
crossings, though I have not tried to prove this rigorously. (One might try counting how many K_5 and K_{3,3} subdivisions are contained in this graph, perhaps, to get some useful lower bound.) My conjecture is that this is the worst case, i.e. that any torus-planar graph can be embedded in the plane with only O(|E|) crossings. I don’t see how to prove this, though it vaguely has a “min-cut” flavour to it.
6 October, 2007 at 9:03 am
Carnival of Math #18 « JD2718
[…] The Crossing Number Inequality Graph Theory “Today I’d like to discuss a beautiful inequality in graph theory, namely the […]
6 October, 2007 at 11:28 am
D. Eppstein
yury: see Wood and Telle, “Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor”, arXiv:math.CO/0604467. It follows from their results that, if a graph can be embedded on a torus and it has bounded vertex degree, then it can be embedded in the plane with a linear number of crossings.
12 October, 2007 at 4:22 am
Rolf Bardeli
Dear Terence,
this article is absolutely lovely.
Could you give some details or a pointer to the literature as to what is meant by “using some analytic number theory to control the size of A*A”?
14 October, 2007 at 3:37 pm
Terence Tao
Dear Rolf,
The recent article
http://front.math.ucdavis.edu/0607.5473
discusses the problem and gives some pointers to the literature. Basically, one needs a lot of (fairly standard) multiplicative estimates about the primes, such as the prime number theorem, and more generally the distribution of integers which are the product of k prime factors.
14 November, 2007 at 5:32 pm
Robert Samal
yury: Regarding the crossing number of a “toroidal” graph: The bounded degree
condition mentioned by D. Eppstein is necessary. To see this, take any
graph that embeds on the torus, but not on the plane (e.g. $K_5$). Then
replace every edge by k parallel edges (or paths, if you prefer simple graphs).
The graph will have O(k) edges, but the crossing number is $k^2$.
17 July, 2008 at 11:53 am
Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more
[…] the surprising connections that were found between the above problems. There is also a very nice post about this material on Terry Tao’s blog. To show you something new I will describe a […]
13 October, 2008 at 1:30 am
Lecture 5: Uniformizing graphs, multi-flows, and eigenvalues « tcs math - some mathematics of theoretical computer science
[…] needed. The beautiful probabilistic proof of Chazelle, Sharir, and Welzl (see the exposition on Terry Tao’s blog) can be appropriately generalized to excluded-minor graphs, and even to families of […]
8 November, 2008 at 12:35 am
Serge
I have established the existence of graphs with crossing number at most 11g but genus equal to g, for every g>=1. It does not look tight. So, do you know tighter series?
12 June, 2009 at 4:06 pm
The Szemerédi-Trotter theorem and the cell decomposition « What’s new
[…] proof of the Szemerédi-Trotter theorem is via the crossing number inequality (as discussed in this previous post), which ultimately relies on Euler’s famous formula ; thus in this argument it is topology […]
14 June, 2009 at 4:36 am
Spencer
Dear Terence,
The link which purports to be to one of Gowers’ papers to do with pseudorandomness/probabilistic methods seems to be sending me to his ‘Two Cultures’ Essay.
To which of his papers was the link intended to point?
Many Thanks,
Spencer
14 June, 2009 at 4:40 am
Spencer
Yep, just realised that perhaps you do mean this essay!
8 July, 2010 at 11:50 am
Matthew Kahle
I struggled for a minute trying to understand why each line was incident to
points in Elekes’ argument. Finally I think I understand:
should probably be
rather than
.
[Corrected, thanks – T.]
20 November, 2010 at 1:11 pm
The Guth-Katz bound on the Erdős distance problem « What’s new
[…] random projection argument. This theorem can be proven by crossing number methods (as discussed in this previous blog post) or by cell decomposition (as discussed in this previous blog post). In both cases, the order […]
8 January, 2011 at 3:28 pm
JamesL
It does not seem that setting A={1,2,…,N} gives the claimed exponential dependence in the lower bound. Ford’s result suggests that |A A| ~ N^2/(log N)^{0.08…}.
The paper of Erdos and Szmeredi uses a different construction:
In particular, Solymosi proves that if |A+A| = O(|A|) then |A \times A| is at least |A|^2/log |A|.
[Hmm, good point. I’ve deleted the relevant remark.]
14 January, 2011 at 9:01 am
Dion, Tobias and Tony
Dear Terry,
While reading your proof of the crossing number inequality we were quite puzzled by the
inequality
$p^4 \hbox{cr}(G) \geq p^2|E| – 3p |V| + 6$.
Surely this cannot hold for all $0< p < 1$. If $p$ is sufficiently small then the LHS is about 0 while the RHS is about 6.
After some discussions we decided that the explanation is that the inequality
$|E| \leq 3|V| – 6$,
is not true for all planar graphs (and consequently (**) $\hbox{cr}(G) \geq |E|-3|V|+6$ is not valid for all graphs).
Counterexamples are the empty graph, the isolated vertex, and the edge.
This means that you cannot just use linearity of expectations to get
${\Bbb E}(\hbox{cr}(G'))\geq {\Bbb E}(|E'|)-3{\Bbb E}(|V'|)+6$
since, for all $0<p<1$, there is a positive chance the inequality (**) is violated.
An easy fix is to use start from the inequality $\hbox{cr}(G) \geq |E|-3|V|$, which is valid for all graphs.
cheers
Dion, Tobias and Tony
14 January, 2011 at 10:44 am
Terence Tao
Thanks for the correction!
18 February, 2011 at 6:42 am
The Szemeredi-Trotter theorem via the polynomial ham sandwich theorem « What’s new
[…] theorem has many short existing proofs, including one via crossing number inequalities (as discussed in this previous post) or via a slightly different type of cell decomposition (as discussed here). The proof given below […]
29 March, 2012 at 6:04 am
On Endre Szemerédi’s Gifts to Computer Science « Windows On Theory
[…] very simple “book proof” (that indeed can be found in page 285 of the book, see also here) was given by Noam Elkies. The proof outline is that, assuming otherwise, one considers the points […]
12 April, 2012 at 12:24 am
Lecture 6 | ASGT
[…] Here are the , and here’s a proof of the crossing number inequality. […]
4 December, 2012 at 9:54 am
David P. Moulton
Hi Terry.
Okay, this post was five years ago, and I just found it, but no one seems to have noticed a little error in something you said.
You said that to optimise the choice of p for the inequality
\hbox{cr}(G) \geq p^{-2} |E| – 3 p^{-3} |V|
you have to solve a cubic. But setting the derivative of the RHS
by p to 0 easily yields p = 9|V| / 2|E| and gives the optimal (for this technique) bound
\hbox{cr}(G) \geq \frac{4|E|^3}{243 |V|^2} whenever |E| \geq 9|V|/2.
Thanks for the nice article–I might have to check out more of your blog!
David
[I’ve edited the text accordingly. There was a
term that was omitted previously, explaining the comment about the cubic. – T.]
5 December, 2012 at 7:46 am
David P. Moulton
Hi Terry.
But didn’t you have to take out the $6p^-4$ term because of the previous comment? They pointed out that you can’t have it in for arbitrary graphs, since it implies that the crossing number always is
positive, which it isn’t. In particular, when you use the probabilistic method, you’ll end up with some subgraphs for which the $+6$ doesn’t apply. I notice, in fact, that in the current version of the post, you don’t have the $+6$ when you take expectations, but you magically put it in when you evaluate. I think you just have to take it out everywhere, and then there’s no cubic to solve.
Thanks,
David
[Ah, I see what happened now. (I was working off of the published version, which predated the previous erratum, and got confused.) It should be fixed now – T.]
10 May, 2013 at 10:05 pm
Bird’s-eye views of Structure and Randomness (Series) | Abstract Art
[…] Drawing networks on a plane (adapted from “The crossing number inequality“) […]
16 May, 2013 at 1:22 am
Drawing networks on a plane | Abstract Art
[…] [1.10] The crossing number inequality […]
11 August, 2013 at 3:17 am
Even more new results! | Some Plane Truths
[…] lemma technique, as introduced by Székely (a nice introduction to this technique can be found in this post by Tao), the new proofs rely on polynomial partitionings (which I just discussed in this series of posts; […]
23 May, 2014 at 8:23 am
Dimension of projected sets and Fourier restriction | Almost Originality
[…] in the plane . Notice that by taking a geometric mean of the terms in the minimum one can get at the RHS, which has a worse exponent than Szemeredi-Trotter above. Indeed, one can prove that in the finite field setting this is optimal, and thus any proof of the Szemeredi-Trotter inequality in the real case can’t rely on algebraic means only – it needs to incorporate some topology or as well. This point is made very clear in the following post by Tao, in which he proves Szemeredi-Trotter via the crossing number inequality: https://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/ […]
11 October, 2014 at 12:27 pm
Problème de distances | Quentin Fortier
[…] Pour sa preuve (particulièrement élégante) je renvoie à un excellent article de Terence Tao sur son blog. […]
7 October, 2019 at 11:01 pm
Configurations with many incidences and no triangles – Cosmin Pohoata
[…] this has been done in an absolutely beautiful indirect manner by Szekely with via the so-called crossing number inequality, however, more modernly, this has also been achieved in various other more practical ways by using […]