[HN Gopher] New Proof Reveals That Graphs with No Pentagons Are ...
___________________________________________________________________
New Proof Reveals That Graphs with No Pentagons Are Fundamentally
Different
Author : theafh
Score : 246 points
Date : 2021-04-26 15:22 UTC (7 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| [deleted]
| WaitWaitWha wrote:
| It would help if the article included at least one real world
| application in layman's terms.
| mFixman wrote:
| Because you are finding the secrets of the Universe? Because
| math is fun?
|
| Not all work has to have a real world application ($$$). It
| would help if the you included at least one real world
| application of writing your comment.
| mjcohen wrote:
| A real world application is getting someone to respond with a
| real world application that would help you make money.
| boomboomsubban wrote:
| Even when math does have profound real world applications
| they aren't always immediately apparent. Think of how many
| millennia work was done on primes before they became a huge
| part of cryptography, though they did have some other uses
| along the way.
| GordonS wrote:
| 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.
| elliekelly wrote:
| This comment resonates with me so much. I remember learning
| how to program, as an adult, and having an epiphany about all
| those times my teachers wrote _f_ (x) and then proceeded to
| write some hodgepodge of numbers and letters. No one had ever
| explained _why_ I would ever need some function for x to spit
| out something else and so I was sort of lost from the very
| beginning when it came to any kind of high level math. Ditto
| for sets and pairs. Basically all of my math education was a
| complete waste until I learned a bit of computer programming
| and could play around with implementing the abstract concepts
| and relate those concepts to practical uses. Then suddenly it
| all made so much more sense!
| Akronymus wrote:
| For me, learning a subject in school is much harder than
| learning it "in the real world" precisely because I often
| lack the connection to it being practical or it otherwise
| just being taught as what instead of why. For me the
| connection of why it is like that makes me actually grok it,
| rather than forgetting it after 5 minutes.
| bordercases wrote:
| There is not one way any piece of mathematics is useful, and
| we don't always know ahead of time what kind of mathematics
| is useful or not.
|
| That's why it's (a) important to know how mathematics can be
| built from concrete instances, like you did with your Quake
| Bot, and (b) that it takes a lot of practice with mathematics
| to know how mathematical modeling is generally done, so that
| you can see how incremental advances in higher mathematics
| might lead to breakthroughs in applied mathematics in the
| future.
|
| Otherwise mathematics fulfills an aesthetic sense for beauty
| and elegance in one's own thinking that most people's minds
| don't seem to support by default. There's nothing wrong with
| that, but it's just as valid an attitude to the subject as
| presuming everything should be motivated by applications at
| first. To those people who enjoy mathematics for its own
| sake, it's a form of play which might organize something
| important in the future, that you otherwise would have missed
| because you're too busy applying some other form of
| mathematics.
| abdullahkhalids wrote:
| As a teacher, I believe applications must be discussed - I am
| a physicist after all.
|
| But I remember my peers asking for applications from math
| teachers when we were in school, but I never saw them ask the
| same from art teachers. Somehow, everyone understood that
| drawing and coloring were just for pleasure and stroking our
| aesthetic sensibilities, and an application was not needed.
| But people rarely think of math the same way. Yet, it's all
| pattern recognition and creation.
| dools wrote:
| Good observation and I think relevant to show the
| difference between how maths is taught and how art is
| taught.
|
| Imagine if you started to learn art by doing shading
| drills, or practising how to use a paint brush by making
| the same stroke over and over again, but never actually
| painting a picture.
| sethhochberg wrote:
| As a person who briefly pursued a degree in a traditional
| engineering discipline before finding my way back to the
| arts (music) and then eventually into a software career, I
| think the difference - at least for me - is that with the
| arts I've never gotten the impression that the fundamentals
| stop being interesting if they're still applied well.
|
| To phrase it another way: practicing scales can be boring.
| But playing a walking bassline is a whole lot more similar
| to scales than it is anything else, and one of the most fun
| things to do with an instrument is to jam with other people
| using the fundamentals you all share.
|
| I never felt the same way with math, because I never felt
| like math allowed me to put anything unique and of my own
| into the mix. Learning the same proof from a book that a
| million other kids taking geometry learned was much less
| interesting to me than transcribing a solo some musician
| played so that I could try to riff on the style they put
| into the world.
|
| Sure, yeah, there's rules in music theory too. You're
| expected to learn them, and get graded on them in tests if
| you study music academically. But I don't know of any
| famous mathematician who ever said something like the
| various Duke Ellington quotes around "if it sounds good, it
| IS good". In the art world, similar riffs on an existing
| idea are everything. In math, they're just... wrong. Or at
| least thats the understanding I had as a student which led
| me to only care about the parts of math that seemed to be
| directly applicable to me, or really intuitive.
| boomboomsubban wrote:
| This sentiment is incredibly common, and it's strange that
| you then get to calculus where the real world applications
| are such an integral part of the subject.
| concreteblock wrote:
| Big reason is that many high school math teachers don't
| really understand math well enough for the job.
| concreteblock wrote:
| To clarify, since I can't edit: This is coming from my
| experience as someone who has taught math to teachers
| getting their master's degree. It sounds mean but I wanted
| to emphasize that the state of early math education is not
| just due to poorly designed curriculum, but because there
| is little incentive for mathematically competent people to
| teach children. (Imo, of course).
| chadcmulligan wrote:
| The other problem in my experience (as a parent and math
| nerd) is that the whole math teaching area is full of
| people who don't know math, so coming in and having a
| math person teach math means you have a huge number of
| arguments you'd have to have.
|
| The only way I know of is to just get after school
| tuition and ignore the school. This is difficult though -
| why do I have to do maths after school? no one else does.
| einpoklum wrote:
| A research grant application maybe? :-P
| _rpd wrote:
| This finding expands our knowledge of graphs. The classic
| application of graphs is logistics, but there are many, many
| more ...
|
| https://en.wikipedia.org/wiki/Graph_theory#Applications
| klyrs wrote:
| I just did a search for "real-world applications of Ramsey
| theory" and this was the closest I got. Sorry.
|
| http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseykings.pdf
| TheMagicHorsey wrote:
| What is a good book to read to learn about graph theory?
| kruuuder wrote:
| If you're looking for a book that shows you the joy of graph
| theory, try Reinhard Diestel's book. It's both deep and
| playful.
| drdeca wrote:
| > the pentagon (or really any five-sided polygon)
|
| An odd line.
|
| Surprising given the quality of the rest of the article.
| lainga wrote:
| maybe it's a regularising "the", like "the Moon" vs. "a
| moon"... "the" regular pentagon, vs., etc.
| thaumasiotes wrote:
| The use of "the" isn't the weird part. The weird part is that
| the article attempts to draw a contrast between "pentagons"
| and "five-sided polygons", which are exactly the same thing.
| frogpelt wrote:
| Pentagons are 5-sided polygons where all the sides are
| equal. Not all 5-sided polygons are pentagons. What am I
| missing?
| thaumasiotes wrote:
| You are missing the definition of a pentagon; try to
| avoid just making up definitions for words you don't
| know.
| MadcapJake wrote:
| What you're describing is called a _regular_ pentagon.
| karmakaze wrote:
| The pointlessness in the distinction is that we're
| talking about graphs defined by their vertices and edges,
| not how they're drawn. (Planar graphs about how they
| 'could' be drawn not withstanding.)
| thaumasiotes wrote:
| No, it isn't; a regular pentagon has all equal side
| lengths (as described) _and_ all equal interior angles
| (not as described).
| waluigi wrote:
| I think what the poster above is saying is that by saying
| "the pentagon" the author is referring to the (unique) 5
| sided regular polygon, as opposed to some random,
| potentially non-regular 5 sided polygon.
| thaumasiotes wrote:
| That would not stop it from being a bizarre error in an
| otherwise decent article. There is no such use.
|
| I interpreted it in the same way as e.g. "the cow has
| four stomachs".
|
| This is a question about graph theory anyway; there are
| no side lengths or interior angles.
| dataflow wrote:
| I don't really tend to think of non-convex five-sided polygons
| as pentagons (even if they technically are), and I'm guessing
| they wanted to emphasis those are included too.
| bena wrote:
| I'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 us all in a room.
|
| I know two people, they know two people, there are two people who
| only know one other person. And then there's the person my wife
| invited who knows no one.
|
| There are certain potential violations that can happen. Let's
| label everyone, I'm A, my guests are B and F, their guests are C
| and E respectively, my wife's guest is D. Our graph is
| essentially E-F-A-B-C and D. I know F-B can't happen because I've
| deliberately chosen people in that manner. And no one other than
| F and B can connect to A as the instructions were to invite
| people I don't know.
|
| C-E-F-C, B-C-E-B, D-E-F-D, B-C-D-B, and C-D-E-C are all possible
| graphs however. But it's also possible that they're not. I'm
| pretty sure I can engineer it so that it won't be.
|
| But this kind of feels like it violates the spirit of the theory
| as it's not a natural group, it's a contrived group.
| ouid wrote:
| 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.
| disabled wrote:
| You may find this interesting:
|
| The mystery of the Bermuda Triangle finally 'solved'?:
| https://www.ancient-code.com/mysterious-hexagonal-clouds-
| beh...
|
| > "Meteorologist, Randy Cerveny explained the phenomenon in
| an interview with the Mirror:"
|
| > "'These types of hexagonal shapes over the ocean are in
| essence air bombs. They are formed by what are called
| microbursts, and they're blasts of air that come down out of
| the bottom of a cloud and then hit the ocean and then create
| waves that can sometimes be massive in size as they start to
| interact with each other.'"
|
| > "Scientists concluded that massive cloud formations were
| appearing over the western parts of Bermuda. This caught the
| attention of Dr. Steve Miller, satellite meteorologist at
| Colorado State University who told the science channel 'You
| don't typically see straight edges with clouds. Most of the
| time, clouds are random in their distribution.'"
|
| > "The Mirror believes this enigmatic weather phenomenon is
| behind the Bermuda Triangle Mystery. To put the mystery of
| the Bermuda triangle in numbers, on average around four
| airplanes and twenty ships o missing every year in the
| Bermuda Triangle."
|
| Interestingly, this shape (as remaining, left-over, air
| bubbles) occurs when I draw up a medication that I self-
| infuse (subcutaneous immunoglobulin), because it is so
| viscous.
| [deleted]
| Rerarom wrote:
| The article (and the theorem) says "there's EITHER a group of
| three who all know each other, OR a group of three who have
| never met"
| daze42 wrote:
| The way it's written this seems like it's exclusive. But it
| appears that both cases are possible at the same time. Maybe
| I'm reading the "OR" too much from the colloquial sense
| instead of the mathematic sense compared to "XOR".
| tiagod wrote:
| > Among those people, there's *either* a group of three who all
| know each other, or a group of three who have never met.
|
| In your example, there are three who have never met (your work
| friend, your hobby friend, and your wife's friend).
| joshuamorton wrote:
| You misread. It's either 3 people who know each other or 3 who
| have never met. Otherwise it's trivial with a 6-cycle.
| nickthemagicman wrote:
| 3 people who know each other = T
|
| 3 people who don't know each other = F
|
| T || F = T
|
| Isn't that just True by default?
|
| Maybe I'm missing the context.
| wongarsu wrote:
| If I know Dan but not Dave, then Dan, Dave and I are not 3
| people who know each other, but we are not 3 people who
| don't know each other either.
| nickthemagicman wrote:
| Thank you for the clarification I was missing out on that
| part of it.
| _jal wrote:
| Let me restate.
|
| 9 of the 6 people know each other = T
|
| 22 of the 6 people don't know each other = F
|
| T || F = T
| alex_smart wrote:
| Why even bother adding an edge?
| verst wrote:
| Right, even trivial with a 6 vertex path. Or a 6 single
| vertex forest
| joshuamorton wrote:
| Honest answer: because I could think of the term for cycle
| more quickly than path.
| alex_smart wrote:
| I meant, why bother adding _any_ edge? Just use the empty
| graph with 6 vertices.
| x3n0ph3n3 wrote:
| > That in a group of at least six people, there are three
| people who all know each other.
|
| You left out the "or there are three people who have never
| met." In your example, C, E, and D have never met each other.
| adrianN wrote:
| Ramsey's theorem is a theorem about coloring. You want to color
| the edges of a complete graph on n vertices with k different
| colors. The theorem says (among other things) that you can't
| color the edges of the complete graph with six vertices with
| just two colors without creating a monochromatic triangle.
| zirkonit wrote:
| > Among those people, there's either a group of three who all
| know each other, or a group of three who have never met.
|
| Or a group of three who have never met. In your example, B, F
| and D have never met.
| bena wrote:
| That's true. I got caught up in the first half of it.
|
| It would be significantly harder to make a ring of six.
| verst wrote:
| Even in a ring of six 3 have never met. :)
| bena wrote:
| See, even now, knowing I'm not thinking about the
| negative result, I'm forgetting the negative result.
| Out_of_Characte wrote:
| "Among those people, there's either a group of three who all
| know each other, or a group of three who have never met."
|
| If your wife's friend knows no one, then you can make a group
| of three in which no one knows each other.
|
| Just pick yourself, and not the person you know from from work
| or your hobbies. or pick the person from work and not their +1
| or yourself. In this manner, in a group of 6. You inescapably
| have one or the other.
| 6gvONxR4sf7o wrote:
| > That in a group of at least six people, there are three
| people who all know each other.
|
| If that's all it was, you could just construct a group of
| complete strangers as a counterexample. But as others
| mentioned, you left out the OR part.
| barbiturique wrote:
| Does 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"
| paulyy_y wrote:
| Arachnophobes beware
| jeffrallen wrote:
| A world without the Pentagon would be fundamentally different
| too. More peaceful...
| voldacar wrote:
| Question 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.
| thanksforfish wrote:
| 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...
| Cerium wrote:
| 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.
| btilly wrote:
| It is worse than that. Here is the calculation.
|
| The number of graphs of size n is 2^(n choose 2). (There are
| n choose 2 pairs of points, each of which could be or not be
| an edge.) If the answer is 43, that's 2^903 which is roughly
| 6.762 * 10^271. If the answer is 48, that's 2^1128 which is
| roughly 3.646 x 10^339.
|
| Naive plus better computers is not enough to tackle this
| problem.
| CrazyStat wrote:
| >The number of graphs of size n is 2^(n choose 2).
|
| This is overcounting by many orders of magnitude. For
| example, there's only one graph with one edge, not (n
| choose 2). For n = 43 you're overcounting these graphs by a
| factor of 903.
|
| Similarly there are only two graphs with two edges (either
| the two edges are connected or not), not ((n choose 2)
| choose 2). For n = 43 you're overcounting these graphs by a
| factor of ~200k.
|
| For graphs with three edges you can have (1) a triangle,
| (2) three edges connected end to end forming a single path,
| (3) three connected edges forming a star, (4) two connected
| edges and one single, or (5) three unconnected edges.
| Compared to your count of ((n choose 2) choose 3), you're
| overcounting by a factor of about 24 million for n=43.
|
| The total (over)count is going to be dominated by graphs
| with approximately (n choose 2)/2 edges, which intuitively
| is where I also expect the overcounting factor to peak.
| btilly wrote:
| I was talking about graphs up to their representation.
| You are talking about graphs up to isomorphism.
| Recognizing that two graphs are isomorphic is a
| potentially tricky problem. Generating them by
| isomorphism class is certainly not going to be the naive
| approach.
|
| But suppose that we are able to do so. How much does this
| do for us? Well, it can help us by a factor of at most
| n!, because you generate isomorphic graphs by permuting
| the vertices. Which for 43 is around
| 6.04152630633738e+52. For 48 is around
| 1.24139155925361e+61. Those are big savings to be sure,
| but are still dwarfed by the size of the search space.
|
| So the next thing to do is to not only try to look at
| each graph up to isomorphism once, but to somehow
| generate them in an order that makes it likely that you
| find cliques or independent sets early. Thereby letting
| you prune out big chunks of the search space. With the
| ability to start different computers out in different
| ranges so we can parallelize the search. But by now we're
| well down on the path to something that is very much not
| a naive search.
| karaterobot wrote:
| >... if the room has at least six people, you can say something
| about them with absolute mathematical certainty... [that it
| contains] either a group of three who all know each other, or a
| group of three who have never met.
|
| Maybe I'm incredibly dense, but this seems tautologically true,
| and not worth mentioning. Could somebody kindly explain what I'm
| missing?
| alanbernstein wrote:
| To a robot, all mathematical truths are tautologies, right?
|
| Perhaps you could imagine reading that statement with both
| occurrences of "three" replaced with blanks. Do you think you
| could confidently fill them in without more than a moment's
| thought?
| Moodles wrote:
| I can't get in your head to know what you're thinking so maybe
| it is obvious to you, but just in case you don't fully
| understand: it may not be obvious that its impossible to have a
| configuration where in the 20 possible groups of 3, someone
| always knows someone else but not everyone knows everyone?
|
| The theorem isn't really saying "it's A or not A". It's saying:
| "it has to be A or B and not anything else".
| q-big wrote:
| > Maybe I'm incredibly dense, but this seems tautologically
| true, and not worth mentioning. Could somebody kindly explain
| what I'm missing?
|
| If this seems so trivial to you, simply write down the proof.
| If you are not really mathematically gifted, you will soon see
| where the problem is ... ;-)
| hoseja wrote:
| One could know the Two, Two know Three but Three not know One.
| That's neither all knowing each other nor them not meeting.
| enkid wrote:
| What he's saying is that there is at least one set where they
| all know each other or they all don't know each other, not
| that any set of three will be that way.
| strgcmc wrote:
| Maybe you're not dense, maybe you're just such a genius that
| pigeonhole principle proofs seem naturally obvious and
| tautologically true to you? :-)
|
| I found this enlightening (particularly "Sketch of a Proof"),
| though I also admit that it seemed fairly straightforward, with
| elegance borne of simplicity rather than of brilliance or
| cleverness:
| https://en.m.wikipedia.org/wiki/Theorem_on_friends_and_stran...
| karaterobot wrote:
| I keep insisting so despite mounting evidence to the
| contrary!
|
| Thank you for the link, this is a very good explanation.
| karmakaze wrote:
| The 'who have never met' isn't the opposite of 'all know each
| other', it's no two people of these three know each other. The
| opposite would be don't all know each other.
|
| If you imagine a six vertices arranged around a point and make
| any number of edges connecting them to represent knows each
| other. For any choice of edges, you can either find 3 vertices
| that are fully connected or you can find three vertices that
| have no connections.
| bloat wrote:
| I would describe it as follows, maybe a little easier to
| visualize. Draw six dots, draw either a red or a blue line
| from every dot to every other dot. You must draw either a
| completely red triangle or a completely blue triangle.
| Personally I don't think it sounds intuitive when stated like
| that!
| austinjp wrote:
| Thanks, personally I found this the easiest way to think
| about it!
| karaterobot wrote:
| Thanks, that clarifies it!
| dooglius wrote:
| It's not true for 5 people if the "has met" graph is a
| pentagon, does your intuition here still work?
| luxuryballs wrote:
| can I get an ELI5?
| mFixman wrote:
| The Erdos-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 has been found for the general conjecture, but
| there has been some progress for some `H`.
|
| The latest paper proves that the conjecture is true if `H` is a
| cycle of 5 graphs. Since proving this was so hard and provided
| so much insight, there's hope that the general conjecture can
| be proved without a lot more work.
|
|
| Here's an actual ELI5:
|
| There's a party where some pairs of guests know each other and
| some don't. A genie told you that there isn't any group of 5
| people that only know two people from that group in a way that
| those relationships form a loop (1 -- 2 -- 3 -- 4 -- 5 -- 1).
|
| Knowing that, you reason that this cannot be a regular party.
| Instead, it has to be one of these two:
|
| 1. A class reunion, where there's a large group of people that
| all know each other.
|
| 2. A group blind date, where there's a large group of people
| where nobody knows anyone.
|
| Being a smart 5-year-old the genie pushes you to publish a
| 19-page paper proving this, but you find out in Hacker News
| that some academics beat you and published it this February.
| Hfjfjdjfjceijfj wrote:
| exponential -> polynomial
| mFixman wrote:
| 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`.
| ball_of_lint wrote:
| I think I'm misunderstanding or you left out an important
| condition.
|
| For your example where H forms a loop, I imagine an element
| of F_H which is a larger loop. Then it could be arbitrarily
| large, have no cliques above size 2, a linear number of
| cliques of size 2, and have only one independent set.
| Dagonfly wrote:
| I'm not an expert, but I think you are confused about what
| 'independent set' means. It's basically 'no vertex pair v,w
| in the set has a edge (v,w)'
|
| So in your loop example, you can take every other vertex in
| the loop and those form an independent set (of size n/2
| ish). And n/2 is in O(n).
| ComodoHacker wrote:
| I guess that's already it. :)
| system2 wrote:
| Today's 5 year olds are all mathematicians anyway.
| Hfjfjdjfjceijfj wrote:
| There's a conjecture about graphs, and the conjecture was
| proven true for a new specific case. So we still don't know
| whether the conjecture is true in general.
|
| For understanding the conjecture itself, I think the
| mathematical description is the easier to comprehend than any
| analogy. See the intro of the Erdos-Hajnal conjecture Wikipedia
| article[1]. Graphs are pretty intuitive mathematical structures
| and the description of the conjecture only uses basic graph
| structures. Although maybe I'm just not clever enough to come
| up with a suitable analogy.
|
| [1]:
| https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conj...
| msoad wrote:
| The article is very approachable actually. Don't be intimidated
| by the title. They explain this very nicely. You don't even
| have to know what a graph is
| visarga wrote:
| and an application ... what can I use it for?
| 101008 wrote:
| First paragraph of the article says something interesting
| that can be useful at parties :)
| politician wrote:
| cryptocurrency
| Mountain_Skies wrote:
| Perhaps not much now but a use for them might come along and
| it will be good that this will be there ready to fill the
| need. It's my understanding that quaternions were mostly a
| curiosity when first described in the mid 1800s but now are
| used extensively in computing. From wikipedia "quaternions
| are used in computer graphics, computer vision, robotics,
| control theory, signal processing, attitude control, physics,
| bioinformatics, molecular dynamics, computer simulations, and
| orbital mechanics." When Sir William Rowan Hamilton first
| described them, he had no concept of most of the above, much
| less that quaternions would be important for them. Good for
| us that he still pushed forward with them.
| dpatterbee wrote:
| 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.
| enchiridion wrote:
| Because most people here are engineers, not mathematicians.
| The newness of mathematics has little to do with its
| utility, so it is reasonable to ask if there are any
| relevant applications.
| visarga wrote:
| I assumed an implied AI application on graphs.
| xmprt wrote:
| 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?
| jerf wrote:
| 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.
| visarga wrote:
| Thanks, great answer
| mFixman wrote:
| I'm impressed by how clear the article is for a layman. I only
| know the very basics of graph theory and Ramsay theory and I
| understood the topic perfectly. This is in comparison to the
| paper [1] which at a glance seems terse and difficult to
| understand.
|
| If anyone likes Ramsay theory and these kind of articles, I
| recommend Erdos' biography "The Man Who Loved Only Numbers".
|
| [1] https://arxiv.org/abs/2102.04994
| strmpnk wrote:
| Quanta Magazine does an excellent job with balancing accessible
| writing and advanced topics. It's just enough to get someone
| interested in the problem and the basic ideas to start thinking
| about it.
___________________________________________________________________
(page generated 2021-04-26 23:00 UTC)