Another Joint Meetings in the books! My first time in San Antonio, until last weekend the largest US city I’d never been to. (Next up: Jacksonville.) A few highlights:
- Ngoc Tran, a postdoc at Austin, talked about zeroes of random tropical polynomials. She’s proved that a random univariate tropical polynomial of degree n has about c log n roots; this is the tropical version of an old theorem of Kac, which says that a random real polynomial of degree n has about c log n real roots. She raised interesting further questions, like: what does the zero locus of a random tropical polynomial in more variables look like? I wonder: does it look anything like the zero set of a random band-limited function on the sphere, as discussed by Sarnak and Wigman? If you take a random tropical polynomial in two variables, its zero set partitions the plane into polygons, which gives you a graph by adjacency: what kind of random graph is this?
- Speaking of random graphs, have you heard the good news about L^p graphons? I missed the “limits of discrete structures” special session which had tons of talks about this, but I ran into the always awesome Henry Cohn, who gave me the 15-minute version. Here’s the basic idea. Large dense graphs can be modeled by graphons; you take a symmetric function W from [0,1]^2 to [0,1], and then your procedure for generating a random graph goes like this. Sample n points x_1,…x_n uniformly from [0,1] — these are your vertices. Now put an edge between x_i and x_j with probability W(x_i,x_j) = W(x_j,x_i). So if W is constant with value p, you get your usual Erdös-Renyi graphs, but if W varies some, you can get variants of E-R, like the much-beloved stochastic blockmodel graphs, that have some variation of edge density. But not too much! These graphon graphs are always going to have almost all vertices with degree linear in n. That’s not at all like the networks you encounter in real life, which are typically sparse (vertex degrees growing sublinearly in n, or even being constant on average) and typically highly variable in degree (e.g. degrees following a power law, not living in a band of constant multiplicative width.) The new theory of L^p graphons is vastly more general. I’ve only looked at this paper for a half hour but I feel like it’s the answer to a question that’s always bugged me; what are the right descriptors for the kinds of random graphs that actually occur in nature? Very excited about this, will read it more, and will give a SILO seminar about it on February 4, for those around Madison.
- Wait, I’ve got still one more thing about random graphs! Russ Lyons gave a plenary about his work with Angel and Kechris about unique ergodicity of the action of the automorphism group of the random graph. Wait, the random graph? I thought there were lots of random graphs! Nope — when you try to define the Erdös-Renyi graph on countably many vertices, there’s a certain graph (called “the Rado graph”) to which your random graph is isomorphic with probability 1! What’s more, this is true — and it’s the same graph — no matter what p is, as long as it’s not 0 or 1! That’s very weird, but proving it’s true is actually pretty easy. I leave it an exercise.
- Rick Kenyon gave a beautiful talk about his work with Aaron Abrams about “rectangulations” — decompositions of a rectangle into area-1 subrectangles. Suppose you have a weighted directed graph, representing a circuit diagram, where the weights on the edges are the conductances of the corresponding wires. It turns out that if you fix the energy along each edge (say, to 1) and an acyclic orientation of the edges, there’s a unique choice of edge conductances such that there exists a Dirichlet solution (i.e. an energy-minimizing assignment of a voltage to each node) with the given energies. These are the fibers of a rational map defined over Q, so this actually gives you an object over a (totally real) algebraic number field for each acyclic orientaton. As Rick pointed out, this smells a little bit like dessins d’enfants! (Though I don’t see any direct relation.) Back to rectangulations: it turns out there’s a gadget called the “Smith Diagram” which takes a solution to the Dirichlet problem on the graph and turns it into a rectangulation, where each edge corresponds to a rectangle, the area of the rectangle is the energy contributed by the current along that edge, the aspect ratio of the rectangle is the conductance, the bottom and top faces of the rectangle correspond to the source and target nodes, the height of a face is the voltage at that node, and etc. Very cool! Even cooler when you see the pictures. For a 40×40 grid, it looks like this: