• Home
  • About Us
  • Contact Us
  • Disclaimer
  • Privacy Policy
  • Terms & Conditions
Wednesday, February 1, 2023
Flyy News
No Result
View All Result
  • Home
  • World
  • Business
  • Entertainment
  • Health
  • Food
  • Politics
  • Tech
  • Science
  • Travel
  • Fashion
  • Lifestyle
  • Home
  • World
  • Business
  • Entertainment
  • Health
  • Food
  • Politics
  • Tech
  • Science
  • Travel
  • Fashion
  • Lifestyle
No Result
View All Result
Flyy News
No Result
View All Result
Home Science

Ramsey Theory Extracts Order from Chaos when Sorting through Confusing Arrangements of Numbers

flyynews by flyynews
November 8, 2022
in Science
0
Ramsey Theory Extracts Order from Chaos when Sorting through Confusing Arrangements of Numbers
0
SHARES
0
VIEWS
Share on FacebookShare on Twitter


Imagine you are hosting a small party for six guests, and it isn’t understood who knows one another and who doesn’t. As it turns out, there’s bound to be at least three people who are complete strangers to one another—or three who are already friends. (We’re not assuming your friends don’t like one another.) So there will always be at least one group of three people who are all either known or completely unknown to one another.

This may not sound too surprising at first, but the more you think about the problem, the more intriguing it becomes. Six people have 15 connections to one another. So, you might ask, how does person A relate to person B? How does A relate to person C? Does B know C? These connections can have one of two values: friends or strangers. This means that with just six guests, there are already 215 (32,768) different ways in which the partygoers can relate to one another. And the math makes the claim that in every possible grouping, there is always a trio in which all know one another or are otherwise complete strangers. Going through each individual case and looking for a trio seems rather cumbersome.

READ ALSO

Gut Bacteria’s Role in Anxiety and Depression: It’s Not Just In Your Head

Mammals That Live Together Live Longer

In fact, figuring this out falls under Ramsey theory, named after the British mathematician Frank Ramsey (1903–1930), who died at the tragically young age of 26. In his short lifetime, however, he managed to develop a branch of mathematics that deals with identifying a certain order in chaos. The aim is to recognize recurring patterns in confusing arrangements, as in the case of our partygoers. The question can be framed from a mathematical point of view: How many guests do you have to invite so that there is at least one group of three people who all know one another or at least one group of three complete strangers?

The whole thing can be solved with figures, or graphs, which are networks of points (also called nodes) and edges (the lines that connect the points). Each person symbolizes a node. The six guests can be arranged in a circle. Now each point is connected. This creates the 15 edges. Depending on whether two people know each other or not, they are colored red (for acquaintances) or blue (for strangers). Now the claim: no matter how you color the edges, you always get a monochromatic triangle—an all-blue or all-red figure.

Now the additional claim made by Ramsey theory: with the six guests just mentioned, no matter how you color the edges, you always get at least one monochromatic triangle—an all-blue or all-red figure. If you try, you will see that such a triangle always appears.

Of course, nobody wants to rummage through the 32,768 possibilities. And doing so would not answer a question posed by Ramsey as to whether six is the smallest number of guests that would inevitably form such a triangle. You can try to solve this problem by changing the number of people invited. If you find triangles colored in a way so that no monochromatic triangle appears at all, then you have found proof to the contrary. If you only invite three guests, two of the people could have met before. So in this case, there is no trio of people who are either all known or strangers to one another—hence there is no monochromatic triangle.

Triangle
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

With four people, it is also easy to find cases in which there is no group of three who re all unknown to or else friends with one another.

Square with two bisecting lines forming an X.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

Even with five guests, there is at least one configuration of friend-stranger connections without a triangle of the same color. So to answer Ramsey’s question about the smallest group of partygoers whose relationships can always be depicted with at least one monochromatic triangle, the number must be more than five. But how much more?

Pentagon with five bisecting lines forming a pentagram.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

What happens when we get to six people? You must now try to color the edges of a graph without creating a single-colored triangle. To do this, you can first pick out a single person A and examine what their relationship to the rest of the guests might be. Let’s say person A is the party’s hostess. Among the invitees, how many friends does she have? There are six different ways of connecting her to the five guests: She might, say, have zero friends, in which case the five invitees are all strangers to her. Or she might have one friend, in which case there are four strangers. This chart shows the various ways six partygoers might connect with the hostess.

The table shows a party hostess’s different relationships with her fiveguests.

The hostess (person A) is friends with at least three people—or at least three people are unknown to her. In a graph, this can be seen by the fact that she always has at least three edges of the same color. Using a concrete example, one can assume that, in one of the configurations shown in the table, the hostess has three red edges, meaning she knows three other guests. Now you can try to color the remaining connections in such a way that a red triangle is avoided among the constellation of 32,768 possible colorings.

Six dots and three red lines.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

So you have to make sure that any two people who know the hostess, don’t know each other—they must have a blue connection between them. But if you mark all these edges in blue, you get a blue triangle! That is, there is no way to avoid a single-color triangle in a six-point graph if all the nodes must be connected. And you can find such a triangle in any larger graph where all points are connected. That means that as soon as you invite more than five guests, there is always a group of three people who all either know one another or do not group of three people who are acquaintances or complete strangers.

Six dots, three red lines and three blue lines.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

Of course, mathematicians are not satisfied with a single result. Instead they try to generalize a problem. So to derive a general case for Ramsey numbers, they would ask, “What is the minimum number of nodes R needs to always find a red m-clique or a blue n-clique. An n-clique denotes a group of n points that are all connected to one another. The resulting number R(m,n) is called the Ramsey number. Surprisingly, very few Ramsey numbers are known. We did just prove that R(3,3) = 6. It could also be shown that R(4,4) = 18. This means that if you invite 18 guests to a party, there will always be a group of four who all either know one another or do not.

It has been unclear for decades how large R(5,5) is, however. In other words, what is the smallest number of guests that you have to invite so that there is always a five-person grouping of all acquaintances or strangers? Experts have been able to narrow down the result: we now know that R(5,5) falls within a range that is less than or equal to 43 nodes on the lower end and less than or equal to 48 nodes at the upper boundary. It might seem like we could simply use a computer to go through all the possible colorings of graphs with 43 nodes to see if there is one that does not contain a group of five of the same color. But in fact, this task exceeds any available computing power!

A graph with 43 nodes that are all connected has 903 edges. These can be either red (friends) or blue (unknown). That’s 2903 possibilities, which is roughly 10272  when rounded off. That’s a 1 followed by 272 zeros, which is unimaginably big. In order to understand how big, one can think about it this way: it is currently assumed that our universe is made up of about 1082 atoms.

Suppose each of those atoms was a calculating machine that could perform as many calculations per second as the currently most powerful supercomputer: a quintillion (1018) calculation steps per second. Let’s assume that every atom could search a quintillion graphs for a group of five in one second—and that the particles would have started doing so right after the big bang, 13.8 billion years in the past. Then they would have had 13.8 x 109 x 365.25 x 24 x 3,600 ≈ 4.35 x 1017 seconds for this task so far. That is, all the atoms in the universe would have examined about 4.35 x 10117 graphs to date—only a tiny fraction of what is left to process.

Thus, mathematicians are looking for a smarter solution to the problem. So far, however, they haven’t found any.

This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.



Source_link

Related Posts

Gut Bacteria’s Role in Anxiety and Depression: It’s Not Just In Your Head
Science

Gut Bacteria’s Role in Anxiety and Depression: It’s Not Just In Your Head

February 1, 2023
Mammals That Live Together Live Longer
Science

Mammals That Live Together Live Longer

February 1, 2023
Scientists Reveal The Most Precise Map of All The Matter in The Universe : ScienceAlert
Science

Scientists Reveal The Most Precise Map of All The Matter in The Universe : ScienceAlert

January 31, 2023
DeepMind AI is as fast as humans at solving previously unseen tasks
Science

DeepMind AI is as fast as humans at solving previously unseen tasks

January 31, 2023
Before ‘Star Trek’ Can Become Reality, We First Have To Protect Planet Earth
Science

Before ‘Star Trek’ Can Become Reality, We First Have To Protect Planet Earth

January 31, 2023
‘A Bear On Mars?’ NASA Spots Trippy Phenomenon On Planet’s Surface
Science

‘A Bear On Mars?’ NASA Spots Trippy Phenomenon On Planet’s Surface

January 31, 2023
Next Post
Pennsylvania on the Middle of the Political Universe

Philadelphia Vote Count Will Take Longer

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

POPULAR NEWS

Angel -Dave Curl – Official Music Video 2022

Angel -Dave Curl – Official Music Video 2022

November 17, 2022
Proud By Cytonic Rhymes – Official Music 2022

Proud By Cytonic Rhymes – Official Music 2022

November 25, 2022
Sweet Bennie Ray – Whole Lot (Official Music Video)

Sweet Bennie Ray – Whole Lot (Official Music Video)

December 22, 2022
SUPER VITAMIN C COLLECTION | STRIVECTIN

SUPER VITAMIN C COLLECTION | STRIVECTIN

December 16, 2022
Rain And Lily Pond Sounds | 10 Hours | Sleep, Relaxation | Dark Screen

Rain And Lily Pond Sounds | 10 Hours | Sleep, Relaxation | Dark Screen

November 14, 2022

About Us

Welcome to Flyy News The goal of Flyy News is to give you the absolute best news sources for any topic! Our topics are carefully curated and constantly updated as we know the web moves fast so we try to as well.

Follow us

Categories

  • Business
  • Entertainment
  • Fashion
  • Food
  • Gaming
  • Health
  • Lifestyle
  • Politics
  • Reviews
  • Science
  • Tech
  • Travel
  • World

Site Links

  • Home
  • About Us
  • Contact Us
  • Disclaimer
  • Privacy Policy
  • Terms & Conditions

Recent News

  • Meet the Living in Yellow Team
  • Easy Baked Chicken Breasts (Juicy and Tender!)
  • Corsair PSUs with side-mounted power connectors are now available
  • Polish leader donates to Ukraine army to end defamation case

Copyright © 2022 Flyynews.com | All Rights Reserved.

No Result
View All Result
  • Home
  • World
  • Business
  • Entertainment
  • Health
  • Food
  • Politics
  • Tech
  • Science
  • Travel
  • Fashion
  • Lifestyle

Copyright © 2022 Flyynews.com | All Rights Reserved.

What Are Cookies
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT