Erdos-Faber-Lovasz Conjecture
Jan. 14th, 2021 06:32 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
joshuazelinskyA preprint proving the Erdos-Faber-Lovasz conjecture (EFL) for sufficiently large n just came out. Initial reactions are positive. The authors, Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, Deryk Osthus, are all serious graph theorists, so simply from an author list this looks like a real attempt. What is EFL and why do we care?
Recall, by a graph, mathematicians and computer scientists mean a collection of points (called vertices or nodes) some of which are connected by edges. For example, one might have a collection of people, some of whom are friends with each other, and we make a graph where we draw an edge between two nodes if the corresponding people are friends with each other.
In a graph, a clique is a collection of nodes of which each node in that collection is connected to every other node in that collection. For example, if we had the friend graph of Alice, Bob, Carol, and Diane, with Alice friends with Bob and Carol, and Bob friends with Carol and Diane, then Alice, Bob and Carol form a clique. The reason we use the word "clique" should be hopefully obvious. (A minor note: We are using connected here in a slightly non-standard fashion. In graph theory we normally speak of two nodes which have an edge between them as being adjacent and use connected to mean that we can follow a path of adjacent nodes between them. But I'm trying to keep the phrasing here as close to regular speech as possible.)
One thing we are interested in with graphs is graph coloring. This is where we try to give each node a color and we want that no two nodes which have an edge between them have the same color. One of the original contexts people cared about this was the Four Color Conjecture, which stated that if one had a map of countries, one never needed more than four colors to color the map, with no two bordering countries the same color. (We are assuming each country is a contiguous section, so nothing like Kalingrad or Alaska allowed). This is equivalent to saying that if I have a graph which is planar, in the sense that I can draw it with no edges, overlapping, then I can color it with at most four colors. Here, each node corresponds to a country, and each edge represents that two countries share a border.
Coloring problems show up in more practical contexts. For example. Suppose one has a school with many students, and some of those students are taking the same classes. We cannot have a student in two classes at the same time. So we wish to schedule the classes so that no two classes are in the same time slot. Then we can make a graph where we think of each class as a node, and two classes have an edge if they share at least one student. Then the minimum number of colors needed to color the graph is the number of time slots needed to fit all the classes in.
Now, for any graph, we can write that graph as a collection of (possibly overlapping) cliques. So let us imagine a graph G which can be written as a collection of n cliques, and none of those n cliques themselves have more than n nodes. Assume further than no two of those n cliques share more than one vertex. (An example of this with n =4 is in this picture ). Then the conjecture is that for any such graph, we do not need more than n colors to color its nodes. This is a famous and notorious difficult problem. Erdos considered it to be one of his favorite graph theory problems.
What this paper claims to show is not the whole EFL, but that if n is large enough, EFL is true. If this is accurate, this is a major breakthrough that will likely have implications about other graph theory problems. I have not had time to read the paper carefully, and it is pretty technical, so I don't know where the sufficiently large n assumption is coming in, although I think it may be coming from their modified use of the Rodl nibble method.
Recall, by a graph, mathematicians and computer scientists mean a collection of points (called vertices or nodes) some of which are connected by edges. For example, one might have a collection of people, some of whom are friends with each other, and we make a graph where we draw an edge between two nodes if the corresponding people are friends with each other.
In a graph, a clique is a collection of nodes of which each node in that collection is connected to every other node in that collection. For example, if we had the friend graph of Alice, Bob, Carol, and Diane, with Alice friends with Bob and Carol, and Bob friends with Carol and Diane, then Alice, Bob and Carol form a clique. The reason we use the word "clique" should be hopefully obvious. (A minor note: We are using connected here in a slightly non-standard fashion. In graph theory we normally speak of two nodes which have an edge between them as being adjacent and use connected to mean that we can follow a path of adjacent nodes between them. But I'm trying to keep the phrasing here as close to regular speech as possible.)
One thing we are interested in with graphs is graph coloring. This is where we try to give each node a color and we want that no two nodes which have an edge between them have the same color. One of the original contexts people cared about this was the Four Color Conjecture, which stated that if one had a map of countries, one never needed more than four colors to color the map, with no two bordering countries the same color. (We are assuming each country is a contiguous section, so nothing like Kalingrad or Alaska allowed). This is equivalent to saying that if I have a graph which is planar, in the sense that I can draw it with no edges, overlapping, then I can color it with at most four colors. Here, each node corresponds to a country, and each edge represents that two countries share a border.
Coloring problems show up in more practical contexts. For example. Suppose one has a school with many students, and some of those students are taking the same classes. We cannot have a student in two classes at the same time. So we wish to schedule the classes so that no two classes are in the same time slot. Then we can make a graph where we think of each class as a node, and two classes have an edge if they share at least one student. Then the minimum number of colors needed to color the graph is the number of time slots needed to fit all the classes in.
Now, for any graph, we can write that graph as a collection of (possibly overlapping) cliques. So let us imagine a graph G which can be written as a collection of n cliques, and none of those n cliques themselves have more than n nodes. Assume further than no two of those n cliques share more than one vertex. (An example of this with n =4 is in this picture ). Then the conjecture is that for any such graph, we do not need more than n colors to color its nodes. This is a famous and notorious difficult problem. Erdos considered it to be one of his favorite graph theory problems.
What this paper claims to show is not the whole EFL, but that if n is large enough, EFL is true. If this is accurate, this is a major breakthrough that will likely have implications about other graph theory problems. I have not had time to read the paper carefully, and it is pretty technical, so I don't know where the sufficiently large n assumption is coming in, although I think it may be coming from their modified use of the Rodl nibble method.
