In math, as in life, small choices can have big consequences. This is especially true in graph theory, a field that studies networks of objects and the connections between them. Here’s a little puzzle to help you see why.
Given six dots, your goal is to connect them to each other with line segments so that there’s always a path between any pair of dots, with no path exceeding two line segments in length. Stop scrolling for a moment and try to work out a solution.
If you solved it, I bet you have something that looks like this:
(click here to reveal the answer)
Notice that this indeed satisfies the requirements of the puzzle. There’s a path between any two dots — what graph theorists call vertices — and no path is longer than two line segments, or edges. (Note: In the puzzle and throughout the column, paths are not allowed to use the same edge more than once.) Your solution might look slightly different, but you’ll end up with the same essential structure, which is easier to see if you move the vertices around a bit.
This “star” structure in graph theory has one central vertex that connects to each of a group of other vertices by a single edge, with no edges between any other vertices. This star isn’t just a solution to our puzzle; it’s the only solution. (You’ll get a chance to prove this in the exercises at the end of the column.)
This puzzle illustrates how local restrictions, like forbidding paths of length 3 or longer, can sometimes force global structures, like the star, to emerge as a result. Leveraging relationships like these can be a powerful tool for understanding graphs and networks, especially when you are looking for certain important structures.
One such structure is a “clique” — a set of vertices where every vertex is directly connected to every other vertex by an edge. Cliques are important because they identify areas of maximum connectivity and dependence. For example, in a network of airline routes, a clique represents a group of cities all connected to each other by direct flights in both directions. This is a source of strength in the network, since you can reach any city in a single flight, and if a route is canceled, you can still connect to any destination with relative ease.
By contrast, an “anti-clique” is a set of vertices where none are directly connected to any others. On a flight map, this represents a group of cities with no direct flights between them. You may still be able to get from point A to point B in an anti-clique, but not directly. You’ll have to travel outside the group first, so getting there will cost you: in time, money or, more generally, efficiency. In a way, anti-cliques identify areas of maximum independence in a network, and for this reason they are also known as independent sets. (You might also see these sets referred to as “cocliques” or “stable sets” elsewhere.)
Finding large cliques or large independent sets, or even just guaranteeing they exist, turns out to be an important part of analyzing graphs and networks. And that’s where the Erdős-Hajnal conjecture comes in. This says that if you forbid certain local structures in graphs, then certain global structures — in particular, relatively large cliques or relatively large independent sets — are unavoidable. It’s one of many open questions attributed to Paul Erdős, the famous mathematical nomad who traveled the world sharing coffee and conjectures with thousands of collaborators. When the Erdős-Hajnal conjecture holds, it provides information that can be used by scientists in fields as diverse as biology, logistics and computer science to draw even stronger conclusions about the global structures of their networks.
We’ve actually the seen Erdős-Hajnal conjecture in action already. In our original puzzle the star shape was unavoidable, and as it turns out, that shape guarantees a large independent set. The five vertices connected to the center of the star have no other connections to each other. You can see this independent set by ignoring the central vertex and the edges that connect to it.
Notice that the existence of this independent set alerts us to a vulnerability in our network. If this were a flight map, and that central city became inaccessible, no one would be able to fly anywhere.
In our puzzle, forbidding the local structure of paths of length 3 or longer guarantees an independent set of size 5. However, this puzzle relies on something that the Erdős-Hajnal conjecture does not, namely that there exists a path between any two vertices. This means that the graph must be “connected,” and this isn’t part of the Erdős-Hajnal conjecture. Is a large independent set unavoidable if such a graph isn’t necessarily connected?
To see if we can avoid a large independent set in our graph, let’s think like a mathematician and start by considering extreme cases. If we aren’t required to connect everything, what if we don’t connect anything?
Adding no edges at all actually gives us the largest independent set possible, all six vertices. In fact, any vertex that doesn’t connect to an edge can be added to any existing independent set to make it bigger, so to get smaller independent sets we probably want every vertex to have at least one edge. What about something like this?
This graph is in two pieces, and you can get an independent set of size 4 by selecting the two vertices on the ends of each piece. Notice how none of the four chosen vertices are connected by an edge to any of the others, thus forming an independent set.
What about a graph like this?
This graph is in three disconnected pieces, and you can get an independent set of size 3 by selecting one vertex from each piece.
This turns out to be the smallest independent set we can achieve under the given conditions. In other words, in a graph with six vertices, forbidding paths of length 3 guarantees an independent set that is at least half the size of the original graph, which is pretty big when it comes to graphs.
There’s actually something more general going on. All the graphs we explored have one important thing in common: They are all collections of stars!
The graph on the left is two stars of three vertices each, and the graph on the right is three stars of two vertices each. Even the graph with no edges can be thought of as six stars of one vertex each. The rule that forbids paths of length 3 forces the graph to be a collection of stars, and this is true whether you start with six vertices or 600. So when it comes to finding independent sets, the only question is how many disconnected stars you end up with.
In general, if you end up with a lot of stars, it’s easy to get a large independent set. Since the stars aren’t connected to each other, you can just choose one vertex from each star, so this guarantees an independent set at least as large as the number of stars. In the example above on the right, you can take one vertex from each of the three stars of size 2 and produce an independent set of size 3.
On the other hand, if you end up with only a few stars, the stars themselves must be big enough to account for all the vertices in the original graph, and we’ve already seen how to get a relatively large independent set from a star — just take everything but the central vertex. For example, if a graph consists of only two stars, then one of the stars is guaranteed to contain at least half the vertices of the original graph, and this guarantees an independent set roughly half the size of the original graph. We can make an even bigger independent set in our example by combining the independent sets from the disconnected stars. (How small could the biggest possible independent set be? See the exercises for more about this.)
In general, for a graph that is just a collection of disconnected stars, a large independent set is unavoidable. Large stars produce large independent sets, but small stars mean lots of stars, which also produce large independent sets. This approach doesn’t just work for our simple example. It also suggests how to handle a more complicated problem.
Suppose you have a graph with n vertices, and you impose the following local restriction: No three vertices can all be connected to each other. This would be like designing a flight map with a particular goal of minimizing locally redundant routes. If you can get between A and B and between B and C, then you aren’t allowed to create a separate, direct route between A and C.
In other words, there can be no cliques of size 3. In geometry terms, the graph is “triangle-free.”
Must a triangle-free graph have a relatively large independent set? The answer is yes, and as before, the secret lies in the stars. We can show that a triangle-free graph with n vertices must have an independent set that is at least roughly $latex sqrt{n}$ in size, which is relatively big by graph theory standards. Let’s walk through the argument using the following triangle-free graph as an example.
Start by picking any vertex in the graph and considering all of its neighbors — the vertices connected to it by an edge.
None of these neighbors of your chosen vertex are connected to each other — because that would make a triangle and this is a triangle-free graph — so each vertex and its set of neighbors essentially forms a star.
Even though this star is connected to other vertices in the graph, we can still use its properties to guarantee a large independent set. The key is to form a star and then remove it and all the edges that connect to it.
Now find a star in the remaining graph and remove it, too.
In this example we are now left with two single vertices — one-vertex stars themselves — and we form an independent set of size 4 by adding the central vertices from the other two stars we found. Since our original graph has nine vertices and $latex sqrt{9}=3$, our independent set of size 4 fits our conjecture.
This argument works in general for any triangle-free graph. The key is to just keep finding and removing stars and the edges that connect to them until you’ve accounted for all the vertices. Once you’ve done that, just count the number of stars.
Let’s say you end up with k stars. If $latex k> sqrt{n}$, then you can form an independent set of size k by taking the central vertex from each star. This works because no two central vertices from any two stars could be connected to each other, as that would have made them neighbors in the original graph.
If $latex k
As with our original example, this result about triangle-free graphs is related to the Erdős-Hajnal conjecture. If a graph is triangle-free, then it can’t have a clique larger than size 2, since a clique of size 3 or more would require a triangle. Forbidding triangles means forbidding large cliques, and this forces large independent sets to emerge, just as the Erdős-Hajnal conjecture predicts.
Mathematicians recently proved much more. The Erdős-Hajnal conjecture has been proved in all cases where the forbidden subgraph consists of four or fewer vertices (like a square or a path of length 4). And in 2021 a group of mathematicians proved that if a graph contains no pentagons — that is, a loop that connects five vertices — then an unusually large clique or an unusually large independent set must exist as a consequence. This surprised some of the mathematicians who proved it, as they expected the Erdős-Hajnal conjecture to be false for pentagons. It was another surprisingly powerful mathematical result that came from thinking locally to act globally.
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/math-that-lets-you-think-locally-but-act-globally-20230721/
