Earlier quoted context omitted.
Why even bother adding an edge?
Honest answer: because I could think of the term for cycle more quickly than path.
I meant, why bother adding any edge? Just use the empty graph with 6 vertices.
New proof reveals that graphs with no pentagons are fundamentally different
41–50 of 116 posts
Re: New proof reveals that graphs with no pentagons are fundamentally different
#42Earlier quoted context omitted.
The Erdős–Hajnal conjecture says that for any graph `H`, then every graph in the set of graphs `F_H` that does not contain `H` as an induced subgraph will either have a polynomial amount of cliques or a polymomial amount of independent sets. The growth rate of the exponent depends on the size of each graph in `F_H` and on some properties `H`. Like with most simple questions in Ramsay theory no proof or contradiction…
exponential -> polynomial
Thanks, edited.
I first understood the conjecture as bounding the exponential function on the size of the graph of an element of `F_H`, but apparently the odd thing is the exponent depends solely on `H`.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#43Earlier quoted context omitted.
and an application ... what can I use it for?
I can't possibly imagine why you would want an application for recently developed mathematics. I would have thought that by now mathematics would have proven its worth enough to not have to justify itself.
I'm doubt there's an immediate application for this result but have there been any similar proofs in the past and what have those been applied to?
Re: New proof reveals that graphs with no pentagons are fundamentally different
#44can I get an ELI5?
and an application ... what can I use it for?
Ramsey theory in a nutshell is about studying what must be true about graphs as they get large in certain ways, because the very size of the graph makes it impossible for the things to be false any longer. My impression is that it tends to be more useful for putting bounds on how good a practical technique can be rather than directly producing said direct techniques.
It's not quite the same as complexity theory in computer science, but it's a pretty close analogy. Complexity theory doesn't necessarily have a lot of direct use, but it's certainly indirectly useful to engineering, and a very useful tool for an engineer to have in their toolbelt for measuring and talking about things that are otherwise too abstract to measure. Even if you aren't inclined to study it directly yourself, don't slag on it, because you benefit from the people who do.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#45I'm stuck on the beginning example. That in a group of at least six people, there are three people who all know each other. I think I can violate that one. I get someone I know from work and someone I know from one of my hobbies that I know don't know each other. To each of them, I have them get someone from their circle that I've never met. Then I get my wife to get someone from her circle I don't know. Then you put…
Other people have explained the part of the question that you missed, but in the interest of helping you clarify your own point, if the group of 6 people are all from different continents, and have never met, then you don't have to spend so much time searching for a counterexample.
The actual question as it is posed is perhaps my favorite problem to show school children. So I'll comment on that too, and maybe it will help you.
I draw 6 non collinear points on a white board in a hexagon, and explain to the students that the goal is to place red or green lines between every pair of points in the hexagon so that no red or green triangles whose vertices are all among the 6 points are formed, (here the green lines represent the relation (have met) and the red lines are (haven't met), since we are forcing every line to be colored, this is just the pair of a graph and it's complement). Most students get the idea pretty quickly, and then even get the idea that there are certain subgraphs which make a solution impossible. For instance, if I have any quadrilateral whose edges are colored red red green green, in order, then the diagonal cannot be colored either red or green. Some bright students start to get the sense that if this were possible to do, then it is likely to be possible to do by taking a graph where the condition doesn't hold and replacing one of the legs of an offending triangle.
They start to get the sense that it can't be done, and sometimes one of the students in the class will try to figure out how many graphs they would have to look through in order to prove this by "brute force". The simplest proof is to notice that a vertex with three edges of the same color incident on it is forbidden, but also is necessarily the case for every vertex.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#46It would help if the article included at least one real world application in layman's terms.
A bit of an aside, but this was always my biggest bugbear when learning maths way back when I was in school - we were never given any practical reasons of why any of it was useful. Even if you explicitly asked the maths teacher "what's it for", they could never give a useful response - it often seemed like they'd never considered this themselves.
Around 13-14 years old, I got interested in building mods for Quake. When I decided to create a bot, I finally understood at least how trigonometry was useful. I won the annual mathematics prize at school that year, and I'm sure it was only because real-world use had gotten me interested.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#47Does that mean something for our usage of graph? Is there folks out-there who would benefit from being able to know stuff about a graph just by knowing it has pentagon in it? ( or vice versa )
The article is enjoyable to read. I smiled at "well, we can't do a general proof at the moment, and it might be a lot of work to do so still. But, if we put a hat on the pentagon, we can prove it"
Re: New proof reveals that graphs with no pentagons are fundamentally different
#48Question for people knowledgable about Ramsey theory - with current computing tech, will we ever be able to find the exact value of R(5,5) within our lifetimes? I've read the famous Erdos quote about R(5,5) vs R(6,6) and he seemed to think that it was at least theoretically possible if the whole human race had to find it quickly or face destruction.
That quote is:
"Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack."
https://blogs.scientificamerican.com/roots-of-unity/moores-l...
Re: New proof reveals that graphs with no pentagons are fundamentally different
#49It would help if the article included at least one real world application in layman's terms.
This finding expands our knowledge of graphs. The classic application of graphs is logistics, but there are many, many more ...
Re: New proof reveals that graphs with no pentagons are fundamentally different
#50Question for people knowledgable about Ramsey theory - with current computing tech, will we ever be able to find the exact value of R(5,5) within our lifetimes? I've read the famous Erdos quote about R(5,5) vs R(6,6) and he seemed to think that it was at least theoretically possible if the whole human race had to find it quickly or face destruction.
It would require an advance in theory. When I took a graph theory course it fascinated me how the Ramsey theory problem goes from paper and pencil complexity to beyond computing power in two steps (R(3,3) = 6, R(4,4) = 18, R(5,5)=(43..48?)).
I once spent some time calculating the effort (but don't have the results handy), a rough number for a naive approach to exhaustively searching the problem space would involve something like 10^200 graphs.