wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/math-that-lets-you-think-locally-but-act-globally-20230721\/#comments<\/a><\/br> 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\u2019s a little puzzle to help you see why.<\/p>\n Given six dots, your goal is to connect them to each other with line segments so that there\u2019s 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.<\/p>\n If you solved it, I bet you have something that looks like this:<\/p>\n Notice that this indeed satisfies the requirements of the puzzle. There\u2019s a path between any two dots \u2014 what graph theorists call vertices \u2014 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\u2019ll end up with the same essential structure, which is easier to see if you move the vertices around a bit.<\/p>\n This \u201cstar\u201d 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\u2019t just a solution to our puzzle; it\u2019s the only solution. (You\u2019ll get a chance to prove this in the exercises at the end of the column.)<\/p>\n 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.<\/p>\n One such structure is a \u201cclique\u201d \u2014 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.<\/p>\n By contrast, an \u201canti-clique\u201d 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\u2019ll 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 \u201ccocliques\u201d or \u201cstable sets\u201d elsewhere.)<\/p>\n 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\u2019s where the Erd\u0151s-Hajnal conjecture comes in. This says that if you forbid certain local structures in graphs, then certain global structures \u2014 in particular, relatively large cliques or relatively large independent sets \u2014 are unavoidable. It\u2019s one of many open questions attributed to Paul Erd\u0151s<\/a>, the famous mathematical nomad who traveled the world sharing coffee and conjectures with thousands of collaborators. When the Erd\u0151s-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.<\/p>\n We\u2019ve actually the seen Erd\u0151s-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. <\/span><\/p>\n 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.<\/p>\n 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\u0151s-Hajnal conjecture does not, namely that there exists a path between any two vertices. This means that the graph must be \u201cconnected,\u201d and this isn\u2019t part of the Erd\u0151s-Hajnal conjecture. Is a large independent set unavoidable if such a graph isn\u2019t necessarily connected?<\/p>\n To see if we can avoid a large independent set in our graph, let\u2019s think like a mathematician and start by considering extreme cases. If we aren\u2019t required to connect everything, what if we don\u2019t connect anything?<\/p>\n Adding no edges at all actually gives us the largest independent set possible, all six vertices. In fact, any vertex that doesn\u2019t 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?<\/p>\n 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.<\/p>\n What about a graph like this?<\/p>\n This graph is in three disconnected pieces, and you can get an independent set of size 3 by selecting one vertex from each piece.<\/p>\n 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.<\/p>\n There\u2019s actually something more general going on. All the graphs we explored have one important thing in common: They are all collections of stars!<\/p>\n 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.<\/p>\n In general, if you end up with a lot of stars, it\u2019s easy to get a large independent set. Since the stars aren\u2019t 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.<\/p>\n 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\u2019ve already seen how to get a relatively large independent set from a star \u2014 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.)<\/p>\n 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\u2019t just work for our simple example. It also suggests how to handle a more complicated problem.<\/p>\n Suppose you have a graph with n<\/em> 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\u2019t allowed to create a separate, direct route between A and C.<\/p>\n In other words, there can be no cliques of size 3. In geometry terms, the graph is \u201ctriangle-free.\u201d<\/p>\n 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<\/em> 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\u2019s walk through the argument using the following triangle-free graph as an example.<\/p>\n Start by picking any vertex in the graph and considering all of its neighbors \u2014 the vertices connected to it by an edge.<\/p>\n None of these neighbors of your chosen vertex are connected to each other \u2014 because that would make a triangle and this is a triangle-free graph \u2014 so each vertex and its set of neighbors essentially forms a star.<\/p>\n 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.<\/p>\n Now find a star in the remaining graph and remove it, too.<\/p>\n In this example we are now left with two single vertices \u2014 one-vertex stars themselves \u2014 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.<\/p>\n 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\u2019ve accounted for all the vertices. Once you\u2019ve done that, just count the number of stars.<\/p>\n Let\u2019s say you end up with k<\/em> stars. If $latex k > sqrt{n}$, then you can form an independent set of size k <\/em>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.<\/p>\n If $latex k < sqrt{n}$, then this smaller number of stars guarantees that at least one of the stars must be relatively big. In fact, it must have at least $latex sqrt{n}$ vertices. Why? Because all n<\/em> vertices of the graph must be found among the k<\/em> stars. If all of the k<\/em> stars had fewer than $latex sqrt{n}$ vertices each, then the total number of vertices in the graph would be less than $latex k times sqrt{n}$. But since $latex k < sqrt{n}$, this means that the total number of vertices in the graph would have to be less than $latex sqrt{n} times sqrt{n} = n$. Since we know the graph has n <\/em>vertices, the assumption that the stars are small leaves some vertices unaccounted for, which means at least one of the stars must have at least $latex sqrt{n}$ vertices. And a star of size $latex sqrt{n}$ guarantees an independent set with a size of at least $latex sqrt{n} -1$, which is roughly $latex sqrt{n}$. (Graph theorists are generally interested in how big a subgraph is relative to the original graph size, so the $latex sqrt{n}$ is much more important than the $latex \u2013 1$.)<\/p>\n As with our original example, this result about triangle-free graphs is related to the Erd\u0151s-Hajnal conjecture. If a graph is triangle-free, then it can\u2019t 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\u0151s-Hajnal conjecture predicts.<\/p>\n Mathematicians recently proved much more. The Erd\u0151s-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<\/a> that if a graph contains no pentagons \u2014 that is, a loop that connects five vertices \u2014 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\u0151s-Hajnal conjecture to be false for pentagons. It was another surprisingly powerful mathematical result that came from thinking locally to act globally.<\/p>\n<\/div>\n <\/br><\/br><\/br><\/p>\n
\nMath That Lets You Think Locally but Act Globally<\/br>
\n2023-07-24 21:58:28<\/br><\/p>\n(click here to reveal the answer)<\/summary>\n<\/details>\n<\/div>\n