The Lovasz number of the plane is about 3.48287

As seen in this comment on Polymath and explicated further in Fernando de Oliveira Filho’s thesis, section 4.4.

I actually spent much of today thinking about this so let me try to explain it in a down-to-earth way, because it involved me thinking about Bessel functions for the first time ever, surely a life event worthy of recording.

So here’s what we’re going to do.  As I mentioned last week, you can express this problem as follows:  suppose you have a map h: R^2 -> V, for some normed vector space V, which is a unit-distance embedding; that is, if |x-x’|_{R^2} = 1, then |h(x)-h(x’)|_V = 1.  (We don’t ask that h is an isometry, only that it preserves the distance-1 set.)

Then let t be the radius of the smallest hypersphere in V containing h(R^2).

Then any graph embeddable in R^2 with all edges of length 1 is sent to a unit-distance graph in V contained in the hyperplane of radius t; this turns out to be equivalent to saying the Lovasz number of G (ok, really I mean the Lovasz number of the complement of G) is at most 1/(1-2t).  So we want to show that t is bounded below 1, is the point.  Or rather:  we can find a V and a map from R^2 to V to make this the case.

So here’s one!  Let V be the space of L^2 functions on R^2 with the usual inner product.  Choose a square-integrable function F on R^2 — in fact let’s normalize to make F^2 integrate to 1 — and for each a in R^2 we let h(a) be the function F(x-a).

We want the distance between F(x-a) and F(x-b) to be the same for every pair of points at distance 1 from each other; the easiest way to arrange that is to insist that F(x) be a radially symmetric function F(x) = f(|x|); then it’s easy to see that the distance between F(x-a) and F(x-b) in V depends only on |a-b|.  We write

g(r) = \int_{\mathbf{R}^2} F(x)F(x-r) dx

so that the squared distance between F(x) and F(x-r) is

\int F(x)^2 dx - \int F(x)F(x-r) dx + \int F(x-r)^2 dx = 2(1-g(r)).

In particular, if two points in R^2 are at distance 1, the squared distance between their images in V is 2(1-g(1)).  Note also that g(0) is the square integral of F, which is 1.

What kind of hypersphere encloses all the points F(x-a) in V?  We can just go ahead and take the “center” of our hypersphere to be 0; since |F| = 1, every point in h(R^2) lies in (indeed, lies on) the sphere of radius 1 around the origin.

Hey but remember:  we want to study a unit-distance embedding of R^2 in V.  Right now, h sends unit distances to the distance 2(1-g(1)), whatever that is.  We can fix that by scaling h by the square root of that number.  So now h sends unit distances to unit distances, and its image is enclosed in a hypersphere of radius

2(1-g(1))^{-1}

The more negative g(1) is, the smaller this sphere is, which means the more we can “fold” R^2 into a small space.  Remember, the relationship between hypersphere number and Lovasz theta is

2t + 1/\theta = 1

and plugging in the above bound for the hypersphere number, we find that the Lovasz theta number of R^2, and thus the Lovasz theta number of any unit-distance graph in R^2, is at most

1-1/g(1).

So the only question is — what is g(1)?

Well, that depends on what g is.

Which depends on what F is.

Which depends on what f is.

And of course we get to choose what f is, in order to make g(1) as negative as possible.

How do we do this?  Well, here’s the trick.  The function G is not arbitrary; if it were, we could make g(1) whatever we wanted.  It’s not hard to see that G is what’s called a positive definite function on R^2.  And moreover, if G is positive definite, there exists some f giving rise to it.  (Roughly speaking, this is the fact that a positive definite symmetric matrix has a square root.)  So we ask:  if G is a positive definite (radially symmetric) function on R^2, and g(0) = 1, how small can g(1) be?

And now there’s an old theorem of (Wisconsin’s own!) Isaac Schoenberg which helpfully classifies the positive definite functions on R^2; they are precisely the functions G(x) = g(|x|) where g is a mixture of scalings of the Bessel function $J_0$:

g(r) = \int_0^\infty J_0(ur) A(u) du

for some everywhere nonnegative A(u).

So g(1) can be no smaller than the minimum value of J_0 on [0,infty], and in fact can be exactly that small if you let A become narrowly supported around the minimum argument.  This is basically just taking g to be a rescaled version of J_0 which achieves its minimum at 1.  That minimum value is about -0.4, and so the Lovasz theta for any unit-distance subgraph on the plane is bounded above by a number that’s about 1 + 1/0.4 = 3.5.

To sum up:  I give you a set of points in the plane, I connect every pair that’s at distance 1, and I ask how you can embed that graph in a small hypersphere keeping all the distances 1.  And you say:  “Oh, I know what to do, just assign to each point a the radially symmetrized Bessel function J_0(|x-a|) on R^2, the embedding of your graph in the finite-dimensional space of functions spanned by those Bessel translates will do the trick!”

That is cool!

Remark: Filho’s thesis does this for Euclidean space of every dimension (it gets more complicated.)  And I think (using analysis I haven’t really tried to understand) he doesn’t just give an upper bound for the Lovasz number of the plane as I do in this post, he really computes that number on the nose.

Tagged , ,

The first pancake is always strangely shaped

Alena Pirutka gave a great algebraic geometry seminar here last week, about (among many other things!) families of smooth projective varieties containing both rational and non-rational members.   We were talking about how you have to give a talk several times before it really starts to be well-put together, and she told me there’s a Russian proverb on the subject:  “The first pancake is always strangely shaped.”  I am totally going to go around saying this from now on.

 

Ocular regression

A phrase I learned from Aaron Clauset’s great colloquium on the non-ubiquity of scale-free networks.  “Ocular regression” is the practice of squinting at the data until it looks linear.

Tagged

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!

 

 

 

 

 

 

Tagged , , ,

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?”)

 

Tagged , ,

Which pictures do children draw with straight lines?

Edray Goins gave a great colloquium today about his work on dessins d’enfants.  And in this talk there was a picture that surprised me.  It was one of the ones on the lower right of this poster.  Here, I’ll put in a screen shot:

Let me tell you what you’re looking at.  You are looking for elliptic curves E admitting a Belyi map f: E -> P^1, which is to say a map ramified only over 0,1, and infinity.  For each such map, the blue graph is f^{-1}([0,1]), the preimage of the line segment joining o and 1 in P^1(R).

In four of these cases, the graph is piecewise linear!  I didn’t know there were examples like this.  Don’t know if this is easy, but:  for which Belyi maps (of any genus, not just genus 1) is f^{-1}([0,1]) a union of geodesics?

Tagged ,

“The Great Ph.D. Scam” (or: Academy Plight Song)

Thanks to the Wayback Machine, here’s my piece from the Boston Phoenix on the MLA, the first feature piece I ever wrote for publication, twenty-one years ago last month.

Who knows if the Wayback Machine is forever?  Just in case, I’m including the text of the piece here.

The Phoenix gave this piece its title, which I think is too fighty.  My title was “Academy Plight Song.”  (Get it?)

I think this holds up pretty well!  (Except if I were writing this today I wouldn’t attach so much physical description to every woman with a speaking part.)

Melani McAlister, the new hire at GWU who appears in the opening scene, is still there as a tenured professor in 2018.  And all these years later, she’s still interested in helping fledgling academics navigate the world of scholarly work; her page “Thinking Twice about Grad School” is thorough, honest, humane, and just great.

Here’s the piece!

The great PhD scam
by Jordan Ellenberg

“We dangle our three magic letters before the eyes of these predestined victims, and they swarm to us like moths to an electric light. They come at a time of life when failure can no longer be repaired easily and when the wounds it leaves are permanent . . . ”
— William James
“The Ph.D. Octopus,” 1903

By nine o’clock, more than 200 would-be professors have piled into the Cotillion Ballroom South at the Sheraton Washington hotel, filling every seat and spilling over into the standing space behind the chairs. They’re young and old, dressed up and down, black and white and other (though mostly white). They’re here to watch Melani McAlister, a 1996 PhD in American Civilization from Brown, explain to a committee of five tenured professors why she ought to be hired at Indiana University.

Everybody looks nervous except McAlister. That’s because, unlike almost everyone else here, she doesn’t need a job; she’s an assistant professor at George Washington University. This interview is a mock-up, a performance put on to inform and reassure the crowd of job-seekers. As McAlister cleanly fields questions about her thesis and her pedagogical strategy, the people in the audience frown and nod, as if mentally rehearsing their own answers to the similar questions they’ll be asked in days to come.

This is night one of the 112th annual meeting of the Modern Language Association, the national organization of professors of English, comparative literature, and living foreign languages. Ten thousand scholars are here in Washington, DC, to attend panels, renew acquaintances, and, most important, to fill open faculty positions. A tenure-track job typically attracts hundreds of applicants; of these, perhaps a dozen will be offered interviews at the MLA; and from that set a handful will be called back for on-campus interviews. For the people who are here “on the market,” that is, trying to become professors of English and so forth, the MLA is the gate to heaven. And, as everyone in the room is aware, the gate is swinging shut.

Continue reading

Tagged , , , ,

Fagone on Cash WinFall

Great, thoroughly reported piece by Jason Fagone (author of The Woman Who Smashed Codes, which everybody says is great) about the Cash WinFall Massachusetts lottery story, which I wrote about at length in How Not To Be Wrong.  My chapter focused on a group of MIT students who became high-volume bettors; Fagone spends more time with Michigan retiree Jerry Selbee, and gets lots of information on the story I wasn’t able to uncover.  That’s why it’s good to have an actual journalist cover these stories!

Tagged , ,

A Supposedly Fun Thing (a book review)

I wrote a review of David Foster Wallace’s book A Supposedly Fun Thing I’ll Never Do Again in 1997 for the late great Boston Phoenix, whose archives don’t seem to be online anymore.  (SOB)

But I have a pdf copy, so here it is, for my own reference, and yours if for some reason you need it!

I should have anticipated this and downloaded all my Phoenix stuff. The first pieces I ever reported were there, a short one about a Michael Moore rally and a long one about the MLA. They’re gone. But wait! I was able to recover the MLA piece from the WayBack Machine.  Thanks, WayBack Machine!  I’ll post that later.

 

 

Tagged , ,
%d bloggers like this: