Show notes
Episode 94 - Jeremy Alm Kevin Knudson & Evelyn Lamb Download 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 i…
Full show notes at the publisher