<input class="spoilerbutton" type="button" value="Episode Transcript (click to expand)" />

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,