We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive
Mathematicians Answer Old Question About Odd Graphs
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    combinatorics

    Mathematicians Answer Old Question About Odd Graphs

    By Kevin Hartnett

    May 19, 2021

    A pair of mathematicians solved a legendary question about the proportion of vertices in a graph with an odd number of connections.
    Comment
    Read Later
    Illustration showing a graph against a purple background, with certain vertices and edges highlighted in orange.

    The highlighted part of this graph forms a subgraph in which all the vertices have an odd number of connections with each other. Mathematicians now know the minimum size of a subgraph guaranteed to have this property in any graph.

    Samuel Velasco/Quanta Magazine

    Kevin Hartnett
    By Kevin Hartnett

    Contributing Writer


    May 19, 2021


    View PDF/Print Mode
    Abstractions blogcombinatoricsgraph theorymathematicsprobabilityAll topics
    red and orange rocket ship surrounded by planet and text says "Hyperjumps! How many planets have you visited today?"red and orange rocket ship surrounded by planet and text says "Hyperjumps! How many planets have you visited today?"

    Introduction

    For decades, mathematicians have debated a simple question about graphs and the number of connections they have. Now, using arguments an undergraduate math student could have come up with, Asaf Ferber of the University of California, Irvine and Michael Krivelevich of Tel Aviv University have finally provided the answer in the form of a proof posted in March.

    “It’s a bit of a surprise, at least for me, that such a combination of clever but basic arguments suffice[d],” said Yair Caro, a mathematician at the University of Haifa.

    Graphs are collections of vertices (dots) connected by edges (lines). After hundreds of years of study, mathematicians are still investigating their basic properties. One concerns the “parity” of a graph’s vertices, meaning whether they are connected to an odd or even number of other vertices.

    Over the last century mathematicians have proved a number of basic results related to parity. In the 1960s Tibor Gallai proved that it’s always possible to split the vertices of a graph into two groups, or subgraphs, such that all the vertices within each subgraph have an even number of connections with each other (ignoring their connections to vertices outside the group) — a property called even “degree.”

    Around the same time he observed that it’s also always possible to split the vertices in a graph into two subgraphs such that the vertices in one all have even degree and the vertices in the other all have odd degree.

    The final option, however, is impossible: There’s no way to split every graph into two subgraphs such that all the vertices within each have odd degree. We know this because in the 1730s Leonhard Euler, perhaps the most prolific mathematician in history, proved that if a group of vertices all have odd degree, then the group must have an even number of vertices. If you’ve split the vertices of a graph into two subgraphs, and all the vertices within each have odd degree, each subgraph must have an even number of vertices and the original unsplit graph can therefore also only have an even number of vertices (because the sum of two even numbers is always even). Which means if the original graph has an odd number of vertices, there’s no way to do the splitting.

    Given the fact that you can’t always split a graph into two subgraphs of odd degree, the next natural question becomes: What’s the largest proportion of the vertices in a graph that you can always be assured will have odd degree?

    “You cannot do odd-odd, and therefore you need to settle for next best thing, which is, let’s do odd with a substantial portion of vertices,” said Krivelevich.

    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    An outdoor photo of Michael Krivelevich in a purple shirt; a photo of Asaf Ferber in a green shirt sitting at a laptop
    An outdoor photo of Michael Krivelevich in a purple shirt; a photo of Asaf Ferber in a green shirt sitting at a laptop

    Michael Krivelevich of Tel Aviv University (left) and Asaf Ferber of the University of California, Irvine, have shown that at least $latex \frac{1}{10,000}$ of the total vertices of any graph form a subgraph in which all vertices have an odd number of connections with each other.

    MFO; Liam Hardiman

    Introduction

    To cement the question, consider a simple example: a graph with three connected vertices in the shape of a triangle. You can isolate any two vertices and see that they share an odd number of connections (1) with each other. Put another way, it’s possible to identify a subgraph of the triangle containing two-thirds of its total vertices, in which all the vertices have odd degree.

    About 50 years ago, mathematicians predicted that for graphs of a given size, there is always a subgraph with all odd degree containing at least a constant proportion of the total number of vertices in the overall graph — like $latex \frac{1}{2}$, or $latex \frac{1}{8}$, or $latex \frac{32}{1,007}$. Whether a graph has 20 vertices or 20 trillion, the size of the subgraph should always meet or exceed the same ratio.

    “The point is, your original graph can be larger and larger and we’re still able to maintain the same proportion,” said Krivelevich.

    But for years no one could find such a specific ratio. In the early 1990s Caro found a ratio that fluctuated with the size of the graph, not a constant one. He proved that if you have N vertices in a graph, there’s a subgraph containing at least $latex \frac{1}{\sqrt{N}}$ of them in which all the vertices have odd degree. Two years later, Alex Scott improved that result to $latex \frac{1}{log N}$, which is much closer to a constant ratio than Caro’s result, but not all the way there.

    “It was close, but no cigar,” said Scott, now a professor at the University of Oxford.

    Progress on the problem languished for almost 30 years until February 2020, when Krivelevich, Ferber’s former graduate adviser, traveled to California to meet with him.

    Ferber had recently revisited the problem about odd graphs, spurred by a tangentially related question one of his colleagues had asked him. He brought the problem up with Krivelevich and they started working through a strategy they’d develop over the next six months.

    Their basic approach — which others before them had also followed — was to sort graphs into three types: “sparse” graphs, where there are lots of vertices that are connected to few other vertices, “dense” graphs with a single vertex connected to many others (relative to the total number of vertices in the graph), and graphs in the middle, with neither of these qualities. Previous work from the 1990s made the sparse and dense cases easy to understand. The hardest part was understanding the middle ground.

    “The question is, what are you doing in between,” said Ferber.

    They came up with a procedure that allowed them to prove that if a graph is neither sparse nor dense, it must have another quality: many small subgraphs that are dense within themselves (though not dense relative to the overall graph) and which are completely disconnected from each other. Proving this last point, that the many small dense subgraphs aren’t connected to each other, was one of the trickiest parts of the project.

    “To show there are no edges between them is quite a pain,” said Ferber.

    Ferber and Krivelevich established that these many small, dense subgraphs can be joined together to create a larger subgraph in which all vertices have odd degree. Now they’d covered all the possibilities — sparse graphs, dense graphs and graphs in between — and showed that they all necessarily contain odd subgraphs of a certain minimum size.

    After a false start in 2020, when Scott let them know of a critical error they were able to circumvent, Ferber and Krivelevich posted the final result in late March 2021. They proved that every graph contains a subgraph, accounting for at least $latex \frac{1}{10,000}$ of its vertices, in which all the vertices have an odd number of connections with each other. Finally, they had their constant fraction.

    (The actual proportion they arrived at was slightly larger, but they rounded it to $latex \frac{1}{10,000}$ for aesthetic reasons. “Imagine if we would write $latex \frac{1}{9,456}$ or some other ugly expression,” Ferber said.)

    From here, there are at least two ways to go. The first is to try and improve the fraction. It’s very likely that the proportion of vertices that must have an odd number of connections is greater than $latex \frac{1}{10,000}$. In the 1990s, Scott speculated it might be as many as $latex \frac{2}{7}$, and future work could chase that number.

    The second involves a host of related questions that have taken on new life following this work.

    Mathematicians want to understand the sizes of collections of vertices with other numeric properties in common — like large groups of vertices, none of which is connected to a number of other vertices that’s evenly divisible by 3 or 5. It’s not clear whether those situations can be characterized by simple fractions too, but it’s encouraging that the proportion of vertices with odd degree can be.

    “[The proof] suggests you should hope for a nice answer there as well,” said Scott.

    Correction: May 19, 2021
    Michael Krivelevich met in person with Asaf Ferber in 2020, not 2019.

    Kevin Hartnett
    By Kevin Hartnett

    Contributing Writer


    May 19, 2021


    View PDF/Print Mode
    Abstractions blogcombinatoricsgraph theorymathematicsprobabilityAll topics
    red and orange rocket ship surrounded by planet and text says "Hyperjumps! How many planets have you visited today?"red and orange rocket ship surrounded by planet and text says "Hyperjumps! How many planets have you visited today?"
    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    The Quanta Newsletter

    Get highlights of the most important news delivered to your email inbox

    Recent newsletters

    Comment on this article

    Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

    Video of a hydra moving against a dark background.

    Next article

    Sleep Evolved Before Brains. Hydras Are Living Proof.
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

    • About Quanta
    • Archive
    • Contact Us
    • Terms & Conditions
    • Privacy Policy
    • Simons Foundation
    All Rights Reserved © 2023