Episode 94 - Jeremy Alm
/
Kevin Knudson: Welcome to my favorite theorem, the math podcast with no quiz at the end. I'm one of your hosts, Kevin Knudson, professor of mathematics at the University of Florida. And here is your other host, fabulous as usual, with a really good zoom background.
Evelyn Lamb: Yes, I am Evelyn Lamb, a freelance math and science writer in Salt Lake City, Utah, and I'm celebrating fall with a nice zoom background that none of our listeners can see of a lovely bike trail near me with decked out in fall colors. So I hope everyone appreciates that.
KK: So judging from Instagram this weekend, you took a train trip somewhere, and it looked really cool.
EL: I did. Yeah, because I'm a freelancer and have quite a bit of schedule flexibility, I do silly things like take the Amtrak for 24 hours to go to Omaha for the weekend and then take it back. And yeah, it was, it was fun.
KK: Why Omaha, just out of curiosity?
EL: Singing, which shouldn't surprise people who know me.
KK: Sure, yeah. Well, I did none of that. I was on an NSF panel last week. That was my big,
EL: Slightly different adventure.
KK: You know, but it's important work. I mean, it really is. And and our listeners, if you happen to get asked to be on an NSF panel, you should do it. It's very interesting and important work. So anyway, now I'm back home, where I’m doing — no, it was here. It was a Zoom panel, but also that was the extent of my week last week. Now that I'm in the Dean's office, which I don't think we've actually mentioned. So I was chair of my department for six years. Now I am an interim associate dean in our college, and one of my responsibilities is that I'm in charge of the college tenure promotion committee, and that committee meets three days a week, at 8am.
EL: Oh, that's great.
KK: That is not my jam at all. And then so twice last week I had T & P first thing in the morning, followed by, you know, seven hours of NSF proposals.
EL: Yeah.
KK: But anyway, I’m glad to be back on Zoom today to welcome our guests. So we're pleased to welcome Jeremy. All Jeremy, why don't you introduce yourself?
Jeremy Alm: Thanks, Kevin and Evelyn. My name is Jeremy Alm. I am Associate Dean for programs in the College of Arts and Sciences at Lamar University in Beaumont, Texas, where it is still quite hot, even the last week of October.
EL: Yes.
JA: Before that, I was department chair at Lamar, and before that, I was department chair at a small college in rural Illinois called Illinois College.
KK: Yeah, cool.
EL: And what's your field of math?
JA: My field of math, so I wrote a dissertation in algebraic logic and universal algebra. Decided I wasn't very good at algebra, started learning combinatorics, so now I solve combinatorial problems that arise in algebraic logic.
EL: Nice. I do think it's funny, if I can interrupt for a moment. It is funny how grad school can do this to us, where you literally wrote a dissertation in algebra. And so what this means, in an objective sense, is, like of the billions of people in the world, you're probably in like the top 100th or 1,000th of 1% of people in knowledge of algebra. And yet your conclusion is “I'm not very good at algebra,” so I have had a similar conclusion that I drew about my field of math as well. So just interesting fact about higher — PhD programs in general, I think,
JA: Yeah. Well, in my case, there's some further evidence, and that is that my main dissertation result was a conditional result, and about four years after I graduated, a Hungarian graduate student proved that my condition, like my additional hypothesis, held in only trivial cases.
EL: Oh, that is a blow, but I'm glad you're using it now in combinatorics.
KK: That sounds like one of those apocryphal stories, right? Where that always gets attributed, like, I don't know, somebody's giving their dissertation defense, and somebody like Milnor, probably not, but somebody like Milnor's in the audience, and they go, “The class of examples here is empty. This is — there's nothing here, you know?”
JA: Well, fortunately, this was only discovered after I graduated.
KK: Right, right, right, right. Well, and, you know, hey, I mean, things like that happen. It's not that big a deal. So, yeah, so Jeremy and I, we go back a little bit. We actually met at an AMS department chairs workshop some number of years ago that I can't even remember anymore. We were both still chairs. I know that. But was it 2019 maybe?
JA: I think it was 2018, but one of those two years.
KK: It was in DC. Question Mark. I don't know, Baltimore? B-more? Yeah. Anyway.
JA: San Diego. Did you go to San Diego?
KK: No. It must be in Baltimore. So anyway, we've kind of kept up a virtual friendship since then. So here we are, and I thought he would — he entertains me, so I thought he would entertain our guests. So, so Jeremy, we asked you on for a purpose. What is your favorite theorem?
JA: So, my favorite theorem is that the Rado graph has certain properties.
EL: Okay, and you know, the next question.
JA: Yes, so I have to have a little bit of setup, okay? Okay, so first I want to talk about random graphs. Cool. Okay. Now imagine you've got a bunch of vertices, or I like to call them dots, because that's usually what they literally are. They're just dots, and we're going to connect two dots, or not. We call that putting an edge in and we're going to flip a coin for each potential edge to decide whether it will be present or absent in the graph. Okay? And usually we assume the coin is fair. Today, we will assume the coin is fair, although you can not assume that, you can make it whatever probability you want.
EL: Yeah.
JA: But if you assume the coin is fair, then you get the uniform distribution on the class of all graphs on some fixed number of vertices, so it's a convenient assumption that the coin be fair.
EL: Right.
JA: Now there are other random graph models. One of the ones that Erdős looked at early on was the one where you sample uniformly from the set of all graphs with a fixed number of vertices and a fixed number of edges, but then you lose independence of edges being in or not, and it's hard to prove things about that model. Even harder is the Barabási-Albert random graph model, where you start with some vertices, and then every time you add a vertex, you attach it to existing vertices, but preferentially, with preference for the the vertices with large degree.
KK: Okay.
JA: And if you do that, instead of getting a sort of binomial degree distribution, like you do with the standard model of random graphs, you get a power law.
EL: Okay, yeah, rich get richer.
JA: Yeah, yes, it's the rich get richer, right? You see this power law in, oh, like, the Facebook graph, the social network graphs, right? Most people are unpopular, and then there are some extremely popular people, but very few of them. And that was a great result in 2000 that showed how a power law degree distribution arises, and it's through preferential attachment and growth, right? But for the rest of this little talk, I just want to talk about the the coin flip model.
EL: Yeah, any graph on that number of vertices is equally likely to any other one.
JA: Correct.
KK: Right, okay.
JA: Ignoring isomorphism, right?
KK: Yeah, okay, sure.
JA: We’ve got, we've got labeled vertices so we can distinguish between two isomorphic graphs.
EL: Yeah, I guess that's kind of important.
JA: Yeah, it's very important. I don’t — I’m not sure what would happen if you worked up to isomorphism.
EL: Sounds hard.
KK: Yeah, let’s ignore that.
JA: Okay, so we're going to connect combinatorics and logic here in just a minute. So I want to briefly talk about first-order formulas. What does that mean? A first-order formula in the language of graphs is built as follows. You have one binary relation symbol that you might think of as a tilde [~]. So x ~ y means that the vertex x is adjacent to the vertex y, and then you have logical symbols — and, or, not, implies. And then you have quantification: for all x, there exists y. Okay, any sentence you can write with those symbols and variables is a first-order sentence in the language of graph theory. Okay. So for example, you could say, for all x, there exists y, x is adjacent to y, and what that says is that no vertex is isolated, right? For all x, there's some y adjacent to it. You could also say there exists x for all y, x is adjacent to y. So that would mean x is adjacent to everything, including itself — which, we're not going to allow loops today. So imagine all the things you can say with first-order formulas in the language of graphs. Well, it turns out that the first- order theory of graphs obeys what's called a zero-one law. And what that means is that any first-order sentence is either almost surely true in all finite graphs or almost surely false in all finite graphs.
EL: That is very strange.
KK: Yeah.
JA: It is.
EL: I think, I think, as a non graph theorist.
JA: Yes. So, for example, almost all finite graphs are connected.
EL: That’s funny. When you first introduced random graphs, I was I almost asked you, like, are those usually connected or not? But then I decided to just wait a moment.
JA: Yup, they are. They are usually connected. In fact, they almost surely have diameter two, which is how you prove they're connected. It turns out, and this still kind of blows my mind. One thing you cannot say with a first order sentence in the language of graphs is “this graph is connected.”
EL: Oh, yeah. Okay. I mean, I, for some reason, I don't know why, maybe it's because I feel like graphs are very tangible and, like, I should be able to understand them quickly. What I want to do right now is first of all, find a way to say that this graph is connected in this first order logic. And second of all, find some proposition that 50% of graphs are going to have, and 50% are not, just to — I don't know why. I don't dislike you, but I want to prove you wrong somehow.
JA: Well, it wouldn't be me you're proving wrong. Whoever proved this theorem, and I actually don't know off the my head, who proved it. So yeah, so we have this zero-one law. So to give an example of a statement that's almost surely false, “this graph is complete,” right? You can say that with a first order sentence, right? For all x, for all y, x not equal to y, implies x adjacent to y.
KK: Sure.
JA: Obviously that's true of few graphs, right?
EL: Yeah.
JA: So that's a good example of the zero part of it. It's almost surely false. Okay, so what do we mean by almost surely true anyway? Well, what we mean is that, if you look — so take the set of all graphs on n vertices and calculate the fraction that satisfy the property, then let n go into infinity. What's the limit? And it turns out, not only does the limit exist, it's always zero or one.
KK: Right.
JA: Okay, that's not true in general. In fact, maybe the simplest example of an intermediate property is for finite groups, the probability of being abelian is, think it's roughly a third or something. So that's a property, you can say that with a first order sentence, x times y equals y times x, and its probability, asymptotically, is intermediate between zero and one. Okay, so this is special to have this zero-one property. Okay, so now I want everyone to imagine we're going to, you know, n is going to infinity, right? And we're getting more and more graphs and the number of edges is, you know, the distribution of number of edges is converging to the normal distribution, and all this nice statistical stuff is going on. Well, what if we sort of take it to the limit and say, okay, n reaches infinity. N is countable. What happens? Well, it turns out that you get, as n goes to infinity, you get more and more of these graphs. But then something changes. When you actually go to the countable random graph, there’s one, and it's called the Rado graph. And what I mean by there's one is that there exists this graph called the Rado graph. And if you actually generate via this coin flip random process, a countably infinite,random graph, with probability one, you get the Rado graph.
KK: Okay, okay, up to isomorphism, right? Or whatever, yeah, or no? Actually, there's just the one, okay.
EL: Yeah, what does the Rado graph mean?
JA: Okay, so there, there are two ways — well, actually, there are a bunch of ways to approach it. I'm only going to talk about two. One is that it's the almost sure result of the countably infinite random process.
KK: Okay.
EL: So, so we're thinking like, let's just say we've got a vertex for every whole number and we want to and then with probability 1/2, we connect, you know, n to m for all n not equal to m. That is that what we mean?
JA: Yes.
EL: Okay.
JA: So that doesn't sound like a definition, though, right, right,
EL: Yeah, because I feel like I could make two different things. You know, in one of them there's a vertex between 2 and 3, and in the other one there isn’t. But somehow this is the same thing?
JA: Oh, well, yes. I mean, you could get different isomorphic copies of the autograph, right? But with right the probability of you getting a graph that is not isomorphic to the one I get is zero.
EL: Yeah. Wild!
JA: Yes. And more cool stuff. Going back to that zero-one law, if you have a first-order formula, it has asymptotic probability 1 if and only if it's true in the Rado graph.
EL: Wait. Can you say that again?
JA: Yes, okay, take a first-order formula in the language of graphs like this graph is complete. That formula is true for almost all finite graphs, if and only if it holds in the Rado graph.
EL: Okay, okay, thank you. So the just takes me an extra time through.
JA: So the Rado graph, in some sense, tells us what all the true first-order statements are in the language of graph theory.
KK: Is it easier to prove these things in the Rado graph? I mean, it's not complete. I get that, but I mean, you know…
JA: I don't think so.
KK: Okay, just kind of a fun fact.
EL: But it might be differently hard and sometimes that's helpful.
KK: Sure.
JA: Yes, so, yeah, I don't, I don't actually know that.
EL: Okay, so, but I feel like I'm marginally, or, you know, provisionally okay with the Rado graph, so yeah.
JA: Here’s something that will make you okay-er with it. Okay. The result of this random process actually has a simple construction that is not random at all.
EL: Okay, great.
JA: Here’s what we do. Our set of vertices is the set of primes that are equivalent to 1 mod 4.
EL: Okay.
JA: Okay, and here's how we determine whether to put an edge in. So you've got two vertices labeled p and q. Because p and 1 are equivalent to 1 mod 4, by quadratic reciprocity, they’re either both quadratic residues modulo each other, or neither. Okay, so you put the edge in if they are quadratic residues modulo each other, and you don't if they aren’t.
EL: Okay.
JA: And that gives you something isomorphic to the Rado graph.
KK: Oh, okay, no way.
JA: I know! It's just ridiculous, right? It's ridiculous. I guess. I mean, the primes are sort of pseudorandom.
KK: Yeah.
JA: You know, I to my very limited understanding, this is essentially how Green and Tao proved that the primes contain arbitrarily long arithmetic progressions.
EL: Yeah, right.
JA: Like, if they were random, then that would have to be true. And they are random enough, right? Even though they're in some sense, not random at all, they’re pseudorandom.
EL: They’re like, yeah, they are, by definition, not random in the least, right? But they act like they are to, like, any way of looking at them, it’s so wild.
JA: Yes, fascinating. Okay, so that that is the Rado graph, yeah. And my theorem is that the Rado graph is, well, in logic, we call it omega-categorical, which means up to isomorphism there's only one countably infinite model of the first-order of graphs, right?
KK: Yeah, so…
JA: Go ahead.
KK: This seems to intersect perfectly for you, right? I mean logic and combinatorics, right? I mean, this is, this is like, if you were going to define something to be like an expert in for you, this is it, right?
JA: Yeah. I mean, I really probably should have done a degree in computer science instead of math, because I like combinatorics, yeah. I like doing machine computations. In a computer science department, I would be, oh, the heavy theory guy, whereas in mathematics, I'm that guy who cheats with a computer.
EL: Hey, we can all get along. We don't need to have factions here. So how does one even begin to go about proving something like this, that your quadratic reciprocity graph construction thing that you just told us is isomorphic to any other random construction I can come up with?
JA: I’m glad you asked that. Okay, so here's the idea of what you do. So it turns out that another way to, sort of obliquely define the Rado graph is the following way. I’m going to define a property and any graph, any countably infinite graph with that property, is isomorphic to the Rado graph. Okay. So given two disjoint subsets of vertices, R and S, there exists a vertex v that is adjacent to every vertex in R and no vertex in S.
EL: So any two disjoint sets of vertices?
JA: Correct. Okay, so you name any set of vertices and then Kevin names a disjoint set of vertices. I have to find a vertex v that is adjacent to all of Evelyn's vertices and none of Kevin's vertices. And if I can always do that, then my graph is isomorphic to the Rado graph.
EL: Okay. We're both skeptical, but okay.
KK: This feels like a weird graph, but okay, all right,
EL: It’s weird property to try to…
KK: It’s because you've got an infinite collection of vertices, right? If everything were finite, this would be bad news, like this would be hard to do.
JA: Right, right. It would be impossible.
KK: But I guess, because you have an infinite number vertices — yeah, right, yeah — for every disjoint pair, you couldn't do it. But because, okay, yeah.
JA: I mean, it's weird.
KK: Yeah, okay.
JA: Another way of thinking of it is that the Rado graph contains every finite graph as an induced subgraph. Okay, anything you can dream up you can find in the Rado graph.
EL: Okay, that sounds like a property of a random graph for sure.
JA: So to go back to the proof about the the construction with the primes, we just have to show that given any two disjoint set of primes, there is some other prime that is a quadratic residue modulo every prime in the first set and no prime in the second set. And if I recall correctly, it's Dirichlet’s theorem on prime progressions, right? Something, you know, wave your hands and it all works.
KK: It’s fine, year.
EL: Call a number theorist or something.
JA: Right. I am not a number theorist.
KK: Right.
JA: I have used some number theory in my work, but I'm definitely not a number theorist. Don't ask me hard number theory questions.
KK: All right. Well, okay, I guess I could kind of see now how one might fall in love with the Rado graph, right? I mean, where'd you first come across this?
JA: I don't remember it. It was definitely not in grad school. It was later just learning about stuff. Oh, actually, I think I was asked to — yeah, I think this is what happened. I had to referee this paper that was a bit of a stretch for me, and I had to look some stuff up. And I encountered this as I was trying to figure out what was going on in this paper that I probably should have not actually refereed, but it looked interesting.
KK: Sure.
JA: Bit of a stretch. These days I would say no to that.
KK: Well, as a journal editor, let me say to all of our listeners, I edit a journal, please accept referee requests. Please? Nobody wants to referee papers anymore. You might learn something!
EL: You might learn something favorite, graph or theorem.
KK: That’s right, that's right, yeah, it's a service to the community and it's good for your brain. So this would be really nice.
EL: Yeah, so I always like to ask if this was kind of a love at first sight theorem or construction. I'm not quite sure you know what part of it would be, love at first sight, but yeah, how did you feel? Did your your love for it grow? Or develop over time?
JA: Oh, it was definitely love at first sight because I just couldn't believe the result. And it actually turns out that the Rado graph is a special case of a more general phenomenon that we don't need to get into. But this notion of a limiting structure that encapsulates all of the properties of the finite structures, that happens in other spaces too.
KK: Cool. All right. Part two, the pairing. So what pairs well with, with the Rado graph?
JA: Okay, well, the Rado graph is something taken to the extreme, right, right. Okay, so my pairing is called Huntsman cheese.
EL: Huntsman cheese. Okay, I'm a little scared.
JA: Okay, so this is something my my parents bring me sometimes when they visit from Wisconsin. It's a big wheel of age cheddar, except inside — it's a pretty tall stack — inside are two layers of blue cheese. Okay, so when you cut into it, it looks like a layer cake.
EL: Yeah!
JA: All right. It's really pretty and it's intense.
EL: Yeah, you’ve got two different kinds of intense cheese flavor, right?
JA: Yes, it's delicious, though.
EL: Yeah, no, I was a little worried there might be, like, organ meats involved or something. In some way, I'm sort of a typical American in that I'm a little not into the offal. So just wasn't sure what these huntsmen were doing with the cheese.
JA: No, I don't know why it's called that.
KK: Yeah.
EL: Oh, that's that sounds good, although maybe hard to like, just a large amount of it would be intimidating.
JA: Oh, yes. I mean, it's very rich, so you don't want to eat very much, yeah?
EL: Good party cheese. Like, get a lot of people together to help you go through it.
JA: Yes, but half of them will refuse to try it.
EL: Yeah, cool. Well, then, I mean, that's great too, because then, once you've got your party, you can start to make graphs of who was already friends and who didn't know each other when they came. Then you can start to do other graph theory. You can find some Ramsey kind of theorem examples, or Ramsey theory kind of stuff. And so you could just like, take this towards Rado graphs and towards Ramsey and other, whatever your your graph theorist heart desires.
KK: I’ve got to try this now. I mean, I was born in Wisconsin. I haven't been back in many, many years. I do not know the Huntsman's cheese, but we’ll have to find some of this.
EL: Put in a special order of the cheese monger.
KK: Yeah, right, yeah, the Florida cheese monger. Actually, we do have a local liquor store that that also does cheese, and they like all these weird — I say weird. I shouldn't say weird, unusual imported cheeses from from England and, you know, the really stinky ones and all of that. I'll have to go there. Maybe they have this Huntsman's cheese.
EL: Yeah.
JA: We like to give our guests a chance to plug anything that they're working on. Or where can we? Can we find you online somewhere? I actually do know some things about Jeremy that, again, our listeners can't see, but he's got this collection of instruments hanging on the wall.
EL: I noticed that. Yeah, do you? So it seems like you've got a variety of stringed instruments behind you. So do you record or, like, publish what you play?
JA: I do. I play several instruments poorly.
KK: I play one poorly.
JA: But yeah, I really like the songwriting process. It's sort of, you know, it scratches an itch that mathematics doesn't necessarily.
EL: Well, mathematicians are creative people, but this is using your creativity in a different direction.
JA: Yes, now that I'm in full time administration, I'm often too tired in the evening to think about mathematical research, but I can strum a ukulele. So it gives me a sort of outlet for creativity that was sort of missing for a while when I went into administration.
EL: Yeah.
KK: So you, you can be found, are you on Spotify?
JA: Yes, yes, right. The band name is the Unbegotten Brothers. And actually, a new single came out just, like, four days ago or something.
EL: Oh, congratulations.
JA: So if you want to hear yet another 12 bar blues, check it out.
KK: Yeah, Jeremy and I have an unpublished 12 bar blues too, that we had a third person lined up to do the singing, and that person never, and we won't out that person, but never followed through with the recording of the vocals.
JA: So we will just, we will shame them in private, not in public.
KK: And I only play rhythm guitar, and again, not especially well, but well enough for 12 bar blues, right? So.
EL: Yeah, it's about enjoying the music-making process.
KK: That’s right.
JA: Yes. I mean, I write it for myself, not for anyone else.
KK: Sure.
JA: But the thing I really want to plug for everyone is an open problem called the chromatic number of the plane.
EL: Ah, I’ve written about this.
JA: Ah, good. There was some shocking, at least shocking to me, progress about four years ago.
EL: Maybe might even be a little longer i could find the date on that article, because I yeah, maybe 20. Yeah, I'm not going to hazard a guess. Time kind of gets weird for me before 2020. Or my memory.
JA: I think it was pre pandemic, though, so yeah. I was absolutely shocked by that result, because I was convinced that the correct answer was four. At least four in Zermelo Fraenkel set theory with choice. I had convinced myself that the answer to the question depended on which axioms of set theory you adopt. So I was shocked when somebody came up with a finite graph with chromatic number five.
EL: Yeah.
JA: I was just like, oh, I couldn't believe it.
EL: Yeah, yeah. Well, that is — yeah, especially if you were really convinced of this and yeah, that it would you, you would require looking at that kind of set theoretic aspect of it in order to eventually prove it, I assume, then, yeah, you got your socks knocked off.
JA: Yes, yeah, I had drawn this analogy. There's an object in mathematical logic that's pretty important, called a non-principal, ultrafilter. Yep, and you can't really construct it. You have to appeal to Zorn's lemma, so you you can't write down. I mean, there are literally no examples.
KK: Right.
JA: But they exist, right? And I kind of thought that there was a four coloring, but we would never be able to describe it.
EL: Right.
JA: And maybe, maybe in different versions of set theory, the answer would be different. In fact, the thing I was originally going to talk about as my favorite theorem is, just very briefly, there exists an infinite, a graph with continuum many vertices, such that in Zermelo Fraenkel set theory with choice, ZFC, the chromatic number is 2. And in ZF plus countable choice, plus the axiom that all subsets of the reels are Lebesgue measurable, the chromatic number is uncountable.
EL: Yeah, I'm glad you didn’t. We would have kicked you off! Yeah, that is wild. So we did maybe skip a little bit for our listeners. So what is the question of the chromatic number of the plane?
JA: Ah. So imagine you are coloring all the points of the plane individually. Okay? And what we're trying to do is not have any two points that are exactly unit distance apart the same color. And it turns out that you need at least four colors. That's an exercise you could assign to undergraduates. Seven suffices. You just, there's a nice little pattern with
EL: Hexagons?
JA: Pentagons? Must be hexagons.
KK: That sounds right.
JA: I haven't thought about this in a little while. But then until 2019, or so, that was all we knew. I mean, we had some conditional results. Like someone showed that if the color classes are all measurable, then you need at least five colors.
EL: Okay.
JA: And then somebody else showed that if you use, like, even nicer sets than measurable sets — I can't remember what it was. Basically like, if you're using sort of rectilinear shapes or something like that, then you need six colors.
KK: Okay.
JA: But no unconditional results, until fairly recently.
EL: So yeah, if you're you know, needing a problem to either put you to sleep or keep you up at night, depending, that's a good one to just kind of try to try to roll around in your head.
KK: Right. Cool. All right. Well, this has been great fun, Jeremy. thanks for joining us.
EL: Yeah, thanks for joining us.
JA: Thank you for having me.
KK: Yeah. It was great. I learned some stuff today. All right, all right. Take care, man.
JA: Okay. Bye.
[outro]
On this episode, we enjoyed talking with Jeremy Alm, a math professor and associate dean at Lamar University, about the Rado graph. Here are some links you might find interesting after you listen.
Alm's website and his band the Unbegotten Brothers
The Rado graph on Wikipedia and the Visual Math Youtube Channel
Omega-categorical theory on Wikipedia
Evelyn's 2018 article about recent progress on the chromatic number of the plane