What is the Lovasz number of the plane?

There are lots of interesting invariants of a graph which bound its chromatic number!  Most famous is the Lovász number, which asks, roughly:  I attach vectors v_x to each vertex x such that v_x and v_y are orthogonal whenever x and y are adjacent, I try to stuff all those vectors into a small cone, the half-angle of the cone tells you the Lovász number, which is bigger and bigger as the smallest cone gets closer and closer to a hemisphere.

Here’s an equivalent formulation:  If G is a graph and V(G) its vertex set, I try to find a function f: V(G) -> R^d, for some d, such that

|f(x) – f(y)| = 1 whenever x and y are adjacent.

This is called a unit distance embedding, for obvious reasons.

The hypersphere number t(G) of the graph is the radius of the smallest sphere containing a unit distance embedding of G.  Computing t(G) is equivalent to computing the Lovász number, but let’s not worry about that now.  I want to generalize it a bit.  We say a finite sequence (t_1, t_2, t_3, … ,t_d) is big enough for G if there’s a unit-distance embedding of G contained in an ellipsoid with major radii t_1^{1/2}, t_2^{1/2}, .. t_d^{1/2}.  (We could also just consider infinite sequences with all but finitely many terms nonzero, that would be a little cleaner.)

Physically I think of it like this:  the graph is trying to fold itself into Euclidean space and fit into a small region, with the constraint that the edges are rigid and have to stay length 1.

Sometimes it can fold a lot!  Like if it’s bipartite.  Then the graph can totally fold itself down to a line segment of length 1, with all the black vertices going to one end and the white vertices going to the other.  And the big enough sequences are just those with some entry bigger than 1.

On the other hand, if G is a complete graph on k vertices, a unit-distance embedding has to be a simplex, so certainly anything with k of the t_i of size at least 1-1/k is big enough.   (Is that an if and only if?  To know this I’d have to know whether an ellipse containing an equilateral triangle can have a radius shorter than that of the circumcircle.)

Let’s face it, it’s confusing to think about ellipsoids circumscribing embedded graphs, so what about instead we define t(p,G) to be the minimum value of the L^p norm of (t_1, t_2, …) over ellipsoids enclosing a unit-distance embedding of G.

Then a graph has a unit-distance embedding in the plane iff t(0,G) <= 2.  And t(oo,G) is just the hypersphere number again, right?  If G has a k-clique then t(p,G) >= t(p,K_k) for any p, while if G has a k-coloring (i.e. a map to K_k) then t(p,G) <= t(p,K_k) for any n.  In particular, a regular k-simplex with unit edges fits into a sphere of squared radius 1-1/k, so t(oo,G) < 1-1/k.

So… what’s the relation between these invariants?  Is there a graph with t(0,G) = 2 and t(oo,G) > 4/5?  If so, there would be a non-5-colorable unit distance graph in the plane.  But I guess the relationship between these various “norms” feels interesting to me irrespective of any relation to plane-coloring.  What is the max of t(oo,G) with t(0,G)=2?

The intermediate t(p,G) all give functions which upper-bound clique number and lower-bound chromatic number; are any of them interesting?  Are any of them easily calculable, like the Lovász number?

Remarks:

1.  I called this post “What is the Lovász number of the plane?” but the question of “how big can t(oo,G) be if t(0,G)=2”? is more a question about finite subgraphs of the plane and their Lovász numbers.  Another way to ask “What is the Lovász number of the plane” would be to adopt the point of view that the Lovász number of a graph has to do with extremizers on the set of positive semidefinite matrices whose (i,j) entry is nonzero only when i and j are adjacent vertices or i=j.  So there must be some question one could ask about the space of positive semidefinite symmetric kernels K(x,y) on R^2  x R^2 which are supported on the locus ||x-y||=1 and the diagonal, which question would rightly be called “What is the Lovász number of the plane?” But I’m not sure what it is.
2. Having written this, I wonder whether it might be better, rather than thinking about enclosing ellipsoids of a set of points in R^d, just to think of the n points as an nxd matrix X and compute the singular values of X^T X, which would be kind of an “approximating ellipsoid” to the points.  Maybe later I’ll think about what that would measure.  Or you can!

 

 

 

 

 

 

The chromatic number of the plane is at least 5

That is:  any coloring of the plane with four colors has two points at distance 1 from each other.  So says a paper just posted by Aubrey de Grey.

The idea:  given a set S of points in the plane, its unit distance graph G_S is the graph whose vertices are S and where two points are adjacent if they’re at distance 1 in the plane.  If you can find S such that G_S has chromatic number k, then the chromatic number of the plane is at least k.  And de Grey finds a set of 1,567 points whose unit distance graph can’t be 4-colored.

It’s known that the chromatic number of the plane is at most 7.  Idle question:  is there any chance of a “polynomial method”-style proof that there is no subset S of the plane whose unit distance graph has chromatic number 7?  Such a graph would have a lot of unit distances, and ruling out lots of repetitions of the same distance is something the polynomial method can in principle do.

Though be warned:  as far as I know the polynomial method has generated no improvement so far on older bounds on the unit distance problem (“how many unit distances can there be among pairs drawn from S?”) while it has essentially solved the distinct distance problem (“how few distinct distances can there be among pairs drawn from S?”)

 

New bounds on curve tangencies and orthogonalities (with Solymosi and Zahl)

New paper up on the arXiv, with Jozsef Solymosi and Josh Zahl.  Suppose you have n plane curves of bounded degree.  There ought to be about n^2 intersections between them.  But there are intersections and there are intersections!  Generically, an intersection between two curves is a node.  But maybe the curves are mutually tangent at a point — that’s a more intense kind of singularity called a tacnode.  You might think, well, OK, a tacnode is just some singularity of bounded multiplicity, so maybe there could still be a constant multiple of n^2 mutual tangencies.

No!  In fact, we show there are O(n^{3/2}).  (Megyesi and Szabo had previously given an upper bound of the form n^{2-delta} in the case where the curves are all conics.)

Is n^{3/2} best possible?  Good question.  The best known lower bound is given by a configuration of n circles with about n^{4/3} mutual tangencies.

Here’s the main idea.  If a curve C starts life in A^2, you can lift it to a curve C’ in A^3 by sending each point (x,y) to (x,y,z) where z is the slope of C at (x,y); of course, if multiple branches of the curve go through (x,y), you are going to have multiple points in C’ over (x,y).  So C’ is isomorphic to C at the smooth points of C, but something’s happening at the singularities of C; basically, you’ve blown up!  And when you blow up a tacnode, you get a regular node — the two branches of C through (x,y) have the same slope there, so they remain in contact even in C’.

Now you have a bunch of bounded degree curves in A^3 which have an unexpectedly large amount of intersection; at this point you’re right in the mainstream of incidence geometry, where incidences between points and curves in 3-space are exactly the kind of thing people are now pretty good at bounding.  And bound them we do.

Interesting to let one’s mind wander over this stuff.  Say you have n curves of bounded degree.  So yes, there are roughly n^2 intersection points — generically, these will be distinct nodes, but you can ask how non-generic can the intersection be?  You have a partition of const*n^2 coming from the multiplicity of intersection points, and you can ask what that partition is allowed to look like.  For instance, how much of the “mass” can come  from points where the multiplicity of intersection is at least r?  Things like that.

 

How many rational distances can there be between N points in the plane?

Terry has a nice post up bout the Erdös-Ulam problem, which was unfamiliar to me.  Here’s the problem:

Let S be a subset of R^2 such that the distance between any two points in S is a rational number.  Can we conclude that S is not topologically dense?

S doesn’t have to be finite; one could have S be the set of rational points on a line, for instance.  But this appears to be almost the only screwy case.  One can ask, more ambitiously:

Is it the case that there exists a curve X of degree <= 2 containing all but 4 points of S?

Terry explains in his post how to show something like this conditional on the Bombieri-Lang conjecture.  The idea:  lay down 4 points in general position.  Then the condition that the 5th point has rational distances from x1,x2,x3, and x4 means that point lifts to a rational point on a certain (Z/2Z)^4-cover Y of P^2 depending on x1,x2,x3,x4.  (It’s the one obtained by adjoining the 4 distances, each of which is a square root of a rational function.)

With some work you can show Y has general type, so under Lang its rational points are supported on a union of curves.  Then you use a result of Solymosi and de Zeeuw to show that each curve can only have finitely many points of S if it’s not a line or a circle.  (Same argument, except that instead of covers of P^2 you have covers of the curve, whose genus goes up and then you use Faltings.)

It already seems hard to turn this approach into a proof.  There are few algebraic surfaces for which we can prove Lang’s conjecture.  But why let that stop us from asking further questions?

Question:  Let S be a set of N points on R^2 such that no M are contained in any line or circle.  What is the maximal number of rational distance among the ~N^2 distances between points of S?

The Erdos-Ulam problem suggests the answer is smaller than N^2.  But surely it’s much smaller, right?  You can get at least NM rational distances just by having S be (N/M) lines, each with M rational points.  Can you do better?

 

An incidence conjecture of Bourgain over fields of positive characteristic (with Hablicsek)

Marci Hablicsek (a finishing Ph.D. student at UW) and I recently posted a new preprint, “An incidence conjecture of Bourgain over fields of finite characteristic.”

The theme of the paper is a beautiful theorem of Larry Guth and Nets Katz, one of the early successes of Dvir’s “polynomial method.”  They proved a conjecture of Bourgain:

Given a set S of points in R^3, and a set of N^2 lines such that

• No more than N lines are contained in any plane;
• Each line contains at least N points of S;

then S has at least cN^3 points.

In other words, the only way for a big family of lines to have lots of multiple intersections is for all those lines to be contained in a plane.  (In the worst case where all the lines are in a plane, the incidences between points and lines are governed by the Szemeredi-Trotter theorem.)

I saw Nets speak about this in Wisconsin, and I was puzzled by the fact that the theorem only applied to fields of characteristic 0, when the proof was entirely algebraic.  But you know the proof must fail somehow in characteristic p, because the statement isn’t true in characteristic p.  For example, over the field k with p^2 elements, one can check that the Heisenberg surface

has a set of p^4 lines, no more than p lying on any plane, and such that each line contains at least p^2 elements of X(k).  If the Guth-Katz theorem were true over k, we could take N = p^2 and conclude that |X(k)| is at least p^6.  But in fact, it’s around p^5.

It turns out that there is one little nugget in the proof of Guth-Katz which is not purely algebraic.  Namely:  they show that a lot of the lines are contained in some surface S with the following property;  at every smooth point s of S, the tangent plane to S at s intersects S with multiplicity greater than 2.  They express this in the form of an assertion that a certain curvature form vanishes everywhere.  In characteristic 0, this implies that S is a plane.  But not so in characteristic p!  (As always, the fundamental issue is that a function in characteristic p can have zero derivative without being constant — viz., x^p.)  All of us who did the problems in Hartshorne know about the smooth plane curve over F_3 with every point an inflection point.  Well, there are surfaces like that too (the Heisenberg surface is one such) and the point of the new paper is to deal with them.  In fact, we show that the Guth-Katz theorem is true word for word as long as you prevent lines not only from piling up in planes but also from piling up in these “flexy” surfaces.

It turns out that any such surface must have degree at least p, and this enables us to show that the Guth-Katz theorem is actually true, word for word, over the prime field F_p.

If you like, you can think of this as a strengthening of Dvir’s theorem for the case of F_p^3.  Dvir proves that a set of p^2 lines with no two lines in the same direction fills up a positive-density subset of the whole space.  What we prove is that the p^2 lines don’t have to point in distinct directions; it is enough to impose the weaker condition that no more than p of them lie in any plane; this already implies that the union of the lines has positive density.  Again, this strengthening doesn’t hold for larger finite fields, thanks to the Heisenberg surface and its variants.

This is rather satisfying, in that there are other situations in this area (e.g. sum-product problems) where there are qualitatively different bounds depending on whether the field k in question has nontrivial subfields or not.  But it is hard to see how a purely algebraic argument can “see the difference” between F_p and F_{p^2}.  The argument in this paper shows there’s at least one way this can happen.

Satisfying, also, because it represents an unexpected application for some funky characteristic-p algebraic geometry!  I have certainly never needed to remember that particular Hartshorne problem in my life up to now.

This Week’s Finds In Number Theory

Twenty years ago yesterday, John Baez posted the first installment of This Week’s Finds in Mathematical Physics.  In so doing, he invented the math blog, and, quite possibly, the blog itself.  A lot of mathematicians of my generation found in John’s blog an accessible, informal, but never dumbed-down window beyond what we were learning in classes, into the messy and contentious ground of current research.  And everybody who blogs now owes him a gigantic debt.

In his honor I thought it would be a good idea to post a “This Week’s Finds” style post of my own, with capsule summaries of a few papers I’ve recently noted with pleasure and interest.  I won’t be able to weave these into a story the way John often did, though!  Nor will there be awesome ASCII graphics.  Nor will any of the papers actually be from this week, because I’m a little behind on my math.NT abstract scanning.

If you run a math blog, please consider doing the same in your own field!  I’ll link to it.

Update:  It begins!  Valeria de Palva offers This Week’s Finds In Categorical Logic.  And Matt Ward, a grad student at UW-Seattle, has This Week’s Finds in Arithmetic Geometry.

1)  “On sets defining few ordinary lines,” by Ben Green and Terry Tao.

The idea that has launched a thousand papers in additive combinatorics:  if you are a set approximately closed under some kind of relation, then you are approximately a set which is actually closed under that kind of relation.  Subset of a group mostly closed under multiplication?  You must be close to an honest subgroup.  Subset of Z with too many pair-sums agreeing?  You have an unusually large intersection with an authentic arithmetic progression.  And so on.

This new paper considers the case of sets in R^2 with few ordinary lines; that is, sets S such that most lines that intersect S at all intersect S in three or more points.  How can you cook up a set of points with this property?  There are various boring ways, like making all the points collinear.  But there’s only one interesting way I can think of:  have the points form an “arithmetic progression” …,-3P,-2P, -P, P,2P,3P, …. in an elliptic curve!  (A finite subgroup also works.)  Then the usual description of the group law on the curve tells us that the line joining two points of S quite often passes through a third.  Green and Tao prove a remarkable quasi-converse to this fact:  if a set has few ordinary lines, it must be concentrated on a cubic algebraic curve!  This might be my favorite “approximately structured implies approximates a structure” theorem yet.

2) “Asymptotic behavior of rational curves,” by David Bourqui.  Oh, I was about to start writing this but when I searched I realized I already blogged about this paper when it came out!  I leave this here because the paper is just as interesting now as it was then…

3) “The fluctuations in the number of points of smooth plane curves over finite fields,” by Alina Bucur, Chantal David, Brooke Feigon, and Matilde Lalin;

“The probability that a complete intersection is smooth,” by Alina Bucur and Kiran Kedlaya;

“The distribution of the number of points on trigonal curves over F_q,” by Melanie Matchett Wood;

“Semiample Bertini theorems over finite fields,” by Daniel Erman and Melanie Matchett Wood.

How many rational points does a curve over F_q have?  We discussed this question here a few years ago, coming to no clear conclusion.  I still maintain that if the curve is understood to vary over M_g(F_q), with q fixed and g growing, the problem is ridiculously hard.

But in more manageable families of curves, we now know a lot more than we did in 2008.

You might guess, of course, that the average number of points should be q+1; if you have to reason to think of Frobenius as biased towards having positive or negative trace, why not guess that the trace, on average, is 0?  Bucur-David-Feigon-Lalin prove that this is exactly the case for a random smooth plane curve.  It’s not hard to check that this holds for a random hyperelliptic curve as well.  But for a random trigonal curve, Wood proves that the answer is different — the average is slightly less than q+2!

Where did the extra point come from?

Here’s one way I like to think of it.  This is very vague, and proves nothing, of course.  The trigonal curve X has a degree-3 map to P^1, which is ramified at some divisor D in P^1.  If D is a random divisor, it has one F_q-point on average.  How many F_q-points on X lie over each rational point P of D?  Well, generically, the ramification is going to be simple, and this means that there are two rational points over D; the branch point, and the unique unramified point.  Over every other F_q-point of D, the Frobenius action on the preimage in X should be a random element of S_3, with an average of one fixed point.  To sum up, in expectation we should see q rational points of X over q non-branch rational points of P^1, and 2 rational points of X over a single rational branch point in P^1, for a total of q+2.

(Erman and Wood, in a paper released just a few months ago, prove much more general results of a similar flavor about smooth members of linear systems on P^1 x P^1 (or other Hirzebruch surfaces, or other varieties entirely) which are semiample; for instance, they may have a map to P^1 which stays constant in degree, while their intersection with another divisor gets larger and larger.)

Most mysterious of all is the theorem of Bucur and Kedlaya, which shows (among other things) that if X is a random smooth intersection of two hypersurfaces of large degree in P^3, then the size of |X(F_q)| is slightly less than q+1 on average.  For this phenomenon I have no heuristic explanation at all.  What’s keeping the points away?

Disks in a box, update

In April, I blogged about the space of small disks in a box.  One question I mentioned there was the following:  if C(n,r) is the space of configurations of n non-overlapping disks of radius r in a box of sidelength 1, what kind of upper bounds on r assure that C(n,r) is connected?  A recent preprint of Matthew Kahle gives some insight into this question: he produces configurations of disks which are stable (each disk is hemmed in by its neighbors) with r on order of 1/n.  (In particular, the density of such configurations goes to 0 as n goes to infinity.)  Note that Kahle’s configurations are not obviously isolated points in C(n,r); it could be, and Kahle suggests it is likely to be, that his configurations can be deformed by moving several disks at once.

Also appearing in Kahle’s paper is the stable 5-disk configuration at left; this one is in fact an isolated point in C(5,r).

More Kahle: another recent paper, with Babson and Hoffman, features the theorem that a random 2-complex on n vertices, where the edges are all present and each 2-face appears with probability p, transitions from non-simply-connected to simply connected when p crosses n^{-1/2}.  This is in sharp contrast with the H_1 of the complex with Z/ ell Z coefficients, which disappears almost surely once p exceeds 2 log n / n, by a result of Meshulam and Wallach.  So in some huge range, the fundamental group is almost surely a big group with no nontrivial abelian quotient!  (I guess this doesn’t formally follow from Meshulam-Wallach unless you have some reasonable uniformity in ell…)

One naturally wonders:  Let pi_1(n,p) be the fundamental group of a random 2-complex on n vertices with facial probability p.   If G is a finite simple group, what is the expected number of surjections from pi_1(n,p) to G?  Does it sharply transition from nonzero to zero?  Is there a range of p in which pi_1(n,p) is almost certainly an infinite group with no finite quotients?

Blogging my orphans: n points in the plane with no three collinear

“Orphans” are things you meant to think about but which you’ve regretfully concluded are never going to rise to the top of the stack. Ideas you never finished having.

Blogging your orphans seems a good use of a math blog, or even a partial math blog like this one — at best, someone else will be able to tell you what’s interesting about your question, or even derive some interest from it themselves; and at worst, someone will be able to explain to you why your question is in fact not interesting, thus setting your mind at ease.

Anyway: the mention of Voronoi cells reminded me of a question that once vexed me about combinatorial geometry in R^2. The question actually arose from an article I wrote about Howard Rosenthal and Keith Poole, political scientists who use data from Congressional votes to map legislators onto low-dimensional Euclidean space. But their method doesn’t really specify points in R^n. When n = 1, for instance, what they get is not a set of 535 points on the real line, but an ordering of the 535 legislators along an axis representing liberalism at one end and conservatism at the other.

What’s really being recorded by the projection of Congress to R^2? I think it’s something like this — for each triple of legislators (x,y,z) you ask: is z to the left or the right of the ray that starts at x and proceeds towards y?

There are n! possible orderings of n points on the line. How many “orderings” are there of n points in the plane?

An algebraic combinatorist might phrase the question like this: Let M be a 3xn matrix with real entries, where the third column consists entirely of 1’s. Suppose every 3×3 minor of M is nonsingular. Then let f(M) be a function from the set of 3-tuples of distinct elements of [1..n] to the set {+1,-1}, where you assign to each 3-tuple (i,j,k) with i < j < k the sign of the determinant of the 3×3 matrix formed by rows i,j,k of M.

Question: As M ranges over 3xn matrices of the given form, how many different functions f(M) are there?

An obvious upper bound is 2^(n choose 3), but this is way too big. Note that if you replace “3” by “2”, the answer to the analogous question is n!.

As a geometer, I’d phrase the question in a different (but I think equivalent) way:

Question: Let X_n be the space of ordered n-tuples of points in R^2 such that no three points are collinear. How many components does X_n have?

Again, if you replace R^2 with R^1 and “no three points are collinear” with “no two points coincide,” you get n!.

Let a(n) be the answer to the questions above (which, if I am not confused, have the same answer.) Then a(3) = 2 and a(4) = 14, and I think maybe a(5) is 252 but I’m not really sure. Combinatorial geometers with a soft spot for orphans, tell me more!