A Path Less Taken to the Peak of the Math World (2017)
The Accidental Apprentice
Huh was born in 1983 in California, where his parents were attending graduate school. They moved back to Seoul, South Korea, when he was two. There, his father taught statistics and his mother became one of the first professors of Russian literature in South Korea since the onset of the Cold War.
After that bad math test in elementary school, Huh says he adopted a defensive attitude toward the subject: He didn’t think he was good at math, so he decided to regard it as a barren pursuit of one logically necessary statement piled atop another. As a teenager he took to poetry instead, viewing it as a realm of true creative expression. “I knew I was smart, but I couldn’t demonstrate that with my grades, so I started to write poetry,” Huh said.
Huh wrote many poems and a couple of novellas, mostly about his own experiences as a teenager. None were ever published. By the time he enrolled at Seoul National University in 2002, he had concluded that he couldn’t make a living as a poet, so he decided to become a science journalist instead. He majored in astronomy and physics, in perhaps an unconscious nod to his latent analytic abilities.
When Huh was 24 and in his last year of college, the famed Japanese mathematician Heisuke Hironaka came to Seoul National as a visiting professor. Hironaka was in his mid-70s at the time and was a full-fledged celebrity in Japan and South Korea. He’d won the Fields Medal in 1970 and later wrote a best-selling memoir called The Joy of Learning, which a generation of Korean and Japanese parents had given their kids in the hope of nurturing the next great mathematician. At Seoul National, he taught a yearlong lecture course in a broad area of mathematics called algebraic geometry. Huh attended, thinking Hironaka might become his first subject as a journalist.
Initially Huh was among more than 100 students, including many math majors, but within a few weeks enrollment had dwindled to a handful. Huh imagines other students quit because they found Hironaka’s lectures incomprehensible. He says he persisted because he had different expectations about what he might get out of the course.
“The math students dropped out because they could not understand anything. Of course, I didn’t understand anything either, but non-math students have a different standard of what it means to understand something,” Huh said. “I did understand some of the simple examples he showed in classes, and that was good enough for me.”
After class Huh would make a point of talking to Hironaka, and the two soon began having lunch together. Hironaka remembers Huh’s initiative. “I didn’t reject students, but I didn’t always look for students, and he was just coming to me,” Hironaka recalled.
Huh tried to use these lunches to ask Hironaka questions about himself, but the conversation kept coming back to math. When it did, Huh tried not to give away how little he knew. “Somehow I was very good at pretending to understand what he was saying,” Huh said. Indeed, Hironaka doesn’t remember ever being aware of his would-be pupil’s lack of formal training. “It’s not anything I have a strong memory of. He was quite impressive to me,” he said.
As the lunchtime conversations continued, their relationship grew. Huh graduated, and Hironaka stayed on at Seoul National for two more years. During that period, Huh began working on a master’s degree in mathematics, mainly under Hironaka’s direction. The two were almost always together. Hironaka would make occasional trips back home to Japan and Huh would go with him, carrying his bag through airports and even staying with Hironaka and his wife in their Kyoto apartment.
“I asked him if he wanted a hotel and he said he’s not a hotel man. That’s what he said. So he stayed in one corner of my apartment,” Hironaka said.
In Kyoto and Seoul, Hironaka and Huh would go out to eat or take long walks, during which Hironaka would stop to photograph flowers. They became friends. “I liked him and he liked me, so we had that kind of nonmathematical chatting,” Hironaka said.
Meanwhile, Hironaka continued to tutor Huh, working from concrete examples that Huh could understand rather than introducing him directly to general theories that might have been more than Huh could grasp. In particular, Hironaka taught Huh the nuances of singularity theory, the field where Hironaka had achieved his most famous results. Hironaka had also been trying for decades to find a proof of a major open problem — what’s called the resolution of singularities in characteristic p. “It was a lifetime project for him, and that was principally what we talked about,” Huh said. “Apparently he wanted me to continue this work.”
In 2009, at Hironaka’s urging, Huh applied to a dozen or so graduate schools in the U.S. His qualifications were slight: He hadn’t majored in math, he’d taken few graduate-level classes, and his performance in those classes had been unspectacular. His case for admission rested largely on a recommendation from Hironaka. Most admissions committees were unimpressed. Huh got rejected at every school but one, the University of Illinois, Urbana-Champaign, where he enrolled in the fall of 2009.
A Crack in a Graph
At Illinois, Huh began the work that would ultimately lead him to a proof of the Rota conjecture. That problem was posed 46 years ago by the Italian mathematician Gian-Carlo Rota, and it deals with combinatorial objects — Tinkertoy-like constructions, like graphs, which are “combinations” of points and line segments glued together.
Consider a simple graph: a triangle.
Mathematicians are interested in the following: How many different ways can you color the vertices of the triangle, given some number of colors and adhering to the rule that whenever two vertices are connected by an edge, they can’t be the same color. Let’s say you have q colors. Your options are as follows:
- q options for the first vertex, because when you’re starting out you can use any color.
- q – 1 options for the adjacent vertex, because you can use any color save the color you used to color the first vertex.
- q – 2 options for the third vertex, because you can use any color save the two colors you used to color the first two vertices.
The total number of colorings will be all options multiplied together, or in this case q x (q – 1) x (q – 2) = q3 – 3q2 + 2q.
That equation is called the chromatic polynomial for this graph, and it has some interesting properties.
Take the coefficients of each term: 1, –3 and 2. The absolute value of this sequence — 1, 3, 2 — has two properties in particular. The first is that it’s “unimodal,” meaning it only peaks once, and before that peak the sequence only ever rises, and after that peak it only ever falls.
The second property is that the sequence of coefficients is “log concave,” meaning that any three consecutive numbers in the sequence follow this rule: The product of the outside two numbers is less than the square of the middle number. The sequence (1, 3, 5) satisfies this requirement (1 x 5 = 5, which is smaller than 32), but the sequence (2, 3, 5) does not (2 x 5 = 10, which is greater than 32).
You can imagine an infinite number of graphs — graphs with more vertices and more edges connected in any number of ways. Every one of these graphs has a unique chromatic polynomial. And in every graph that mathematicians have ever studied, the coefficients of its chromatic polynomial have always been both unimodal and log concave. That this fact always holds is called “Read’s conjecture.” Huh would go on to prove it.
Read’s conjecture is, in a sense, deeply counterintuitive. To understand why, it helps to understand more about how graphs can be taken apart and put back together. Consider a slightly more complicated graph — a rectangle:
The chromatic polynomial of the rectangle is harder to calculate than that of the triangle, but any graph can be broken up into subgraphs, which are easier to work with. Subgraphs are all the graphs you can make by deleting an edge (or edges) from the original graph:
Or by contracting two vertices into one:
The chromatic polynomial of the rectangle is equal to the chromatic polynomial of the rectangle with one edge deleted minus the chromatic polynomial of the triangle. This makes intuitive sense when you recognize that there should be more ways to color the rectangle with the deleted edge than the rectangle itself: The fact that the top two points aren’t connected by an edge gives you more coloring flexibility (you can, for instance, color them the same color, which you’re not allowed to do when they’re connected). Just how much flexibility does it give you? Precisely the number of coloring options for the triangle.
The chromatic polynomial for any graph can be defined in terms of the chromatic polynomials of subgraphs. And the coefficients of all of these chromatic polynomials are always log concave.
Yet when you add or subtract two log concave sequences, the resulting sequence is usually not itself log concave. Because of this, you’d expect log concavity to disappear in the process of combining chromatic polynomials. Yet it doesn’t. Something else is going on. “This is what made people curious of this log concavity phenomenon,” Huh said.
from Hacker News https://ift.tt/2PRd5Nq