* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Monday, June 2, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Rising stars: Young classical musicians surging on social media – Yahoo

    Meet the Next Generation of Classical Music Sensations Making Waves on Social Media!

    Devin Harjes Dies: ‘Manifest’ & ‘Boardwalk Empire’ Actor Was 41 – WyomingNews.com

    Tragic Loss: Devin Harjes, Star of ‘Manifest’ and ‘Boardwalk Empire,’ Passes Away at 41

    Why Starz Entertainment Stock Soared Today – The Motley Fool

    Unpacking the Surge: What Fueled Starz Entertainment’s Stock Explosion Today!

    Unveiling the Enigmatic: First Looks at Destruction and Puck in ‘The Sandman

    Jackie Chan Reveals This Family Member ‘Never Watched’ The Whole Of Any Of His Movies – Yahoo

    Jackie Chan Reveals This Family Member ‘Never Watched’ The Whole Of Any Of His Movies – Yahoo

    Mavs CEO holds firm on new arena, entertainment district in Dallas – Dallas News

    Mavs CEO Stands Strong on Vision for New Arena and Entertainment District in Dallas

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    ROLAND’S NEW WIRELESS TRIGGER TECHNOLOGY, PORTER & DAVIES ON TOUR, NEW 64 AUDIO ASPIRE UNIVERSAL IEM MODELS, WAVES FREE PLUGIN PACK – Modern Drummer Magazine

    ROLAND’S NEW WIRELESS TRIGGER TECHNOLOGY, PORTER & DAVIES ON TOUR, NEW 64 AUDIO ASPIRE UNIVERSAL IEM MODELS, WAVES FREE PLUGIN PACK – Modern Drummer Magazine

    This giant microwave may change the future of war – MIT Technology Review

    Revolutionizing Warfare: The Impact of a Game-Changing Giant Microwave

    Bajeed Pattan Joins Forbes Technology Council as Innovation Leader – PRWeb

    Bajeed Pattan Takes the Helm as Innovation Leader at Forbes Technology Council!

    Lafayette Regional Technology Council – Tech Leadership That’s Homegrown and Future-Focused – Discover Lafayette

    Lafayette Regional Technology Council – Tech Leadership That’s Homegrown and Future-Focused – Discover Lafayette

    Drone technology demo in Cambria County showcases future of lifesaving medical deliveries – local21news.com

    Revolutionizing Healthcare: Drone Technology Takes Flight for Lifesaving Medical Deliveries in Cambria County

    Revolutionary Harvesting Technology Promises to Slash CAR-T Manufacturing Costs!

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Rising stars: Young classical musicians surging on social media – Yahoo

    Meet the Next Generation of Classical Music Sensations Making Waves on Social Media!

    Devin Harjes Dies: ‘Manifest’ & ‘Boardwalk Empire’ Actor Was 41 – WyomingNews.com

    Tragic Loss: Devin Harjes, Star of ‘Manifest’ and ‘Boardwalk Empire,’ Passes Away at 41

    Why Starz Entertainment Stock Soared Today – The Motley Fool

    Unpacking the Surge: What Fueled Starz Entertainment’s Stock Explosion Today!

    Unveiling the Enigmatic: First Looks at Destruction and Puck in ‘The Sandman

    Jackie Chan Reveals This Family Member ‘Never Watched’ The Whole Of Any Of His Movies – Yahoo

    Jackie Chan Reveals This Family Member ‘Never Watched’ The Whole Of Any Of His Movies – Yahoo

    Mavs CEO holds firm on new arena, entertainment district in Dallas – Dallas News

    Mavs CEO Stands Strong on Vision for New Arena and Entertainment District in Dallas

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    ROLAND’S NEW WIRELESS TRIGGER TECHNOLOGY, PORTER & DAVIES ON TOUR, NEW 64 AUDIO ASPIRE UNIVERSAL IEM MODELS, WAVES FREE PLUGIN PACK – Modern Drummer Magazine

    ROLAND’S NEW WIRELESS TRIGGER TECHNOLOGY, PORTER & DAVIES ON TOUR, NEW 64 AUDIO ASPIRE UNIVERSAL IEM MODELS, WAVES FREE PLUGIN PACK – Modern Drummer Magazine

    This giant microwave may change the future of war – MIT Technology Review

    Revolutionizing Warfare: The Impact of a Game-Changing Giant Microwave

    Bajeed Pattan Joins Forbes Technology Council as Innovation Leader – PRWeb

    Bajeed Pattan Takes the Helm as Innovation Leader at Forbes Technology Council!

    Lafayette Regional Technology Council – Tech Leadership That’s Homegrown and Future-Focused – Discover Lafayette

    Lafayette Regional Technology Council – Tech Leadership That’s Homegrown and Future-Focused – Discover Lafayette

    Drone technology demo in Cambria County showcases future of lifesaving medical deliveries – local21news.com

    Revolutionizing Healthcare: Drone Technology Takes Flight for Lifesaving Medical Deliveries in Cambria County

    Revolutionary Harvesting Technology Promises to Slash CAR-T Manufacturing Costs!

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
Earth-News
No Result
View All Result
Home Science

In Highly Connected Networks, There’s Always a Loop

June 7, 2024
in Science
In Highly Connected Networks, There’s Always a Loop
Share on FacebookShare on Twitter

So instead of trying to produce a general algorithm for finding Hamiltonian cycles, some mathematicians have focused on the easier problem of proving that particular types of graphs contain such cycles. In 2002, Michael Krivelevich of Tel Aviv University and Benny Sudakov, now at the Swiss Federal Institute of Technology Zurich, conjectured that an important class of graphs called expander graphs all contain Hamiltonian cycles. In February, together with four other mathematicians, Sudakov succeeded in proving the conjecture he’d first ventured over two decades earlier.

In Search of Cycles

Krivelevich and Sudakov’s conjecture punctuated a long series of attempts to untangle the conditions that would guarantee a Hamiltonian cycle. Back in 1952, Gabriel Dirac, a Danish mathematician (and stepson of the famous physicist Paul Dirac), proved that every graph with n points, or nodes, where each node is connected to at least n/2 others contains a Hamiltonian cycle. But this is a lot of lines (more commonly called edges). Over the years, mathematicians worked to reduce the number of edges Hamiltonian graphs had to have. In 1976, the Hungarian mathematician Lajos Pósa proved that certain graphs built by randomly drawing edges were virtually guaranteed to contain Hamiltonian cycles. By 2001, Krivelevich and Sudakov, together with two other colleagues, as well as another competing group, had proved similar results about a different class of graphs.

Krivelevich and Sudakov thought they knew why graphs made at random were likely to contain a Hamiltonian cycle. Random graphs have two key properties. The first property concerns what happens if you examine two large, nonoverlapping groups of nodes within the graphs. In a random graph, it’s very likely that there will be at least one edge connecting the groups.

The second property involves small groups of nodes. Take a small group of nodes, and call it A. Now enlarge it by adding every node that’s connected to something in A. Mathematicians call this larger group the “neighborhood” of A. In random graphs, the neighborhood of A is likely to be far larger than A itself. So mathematicians say that A “expands” to a large neighborhood.

Graphs with these two properties — where large groups of nodes are likely to share an edge, and where small groups of nodes expand into much larger groups — are called expander graphs. If the neighborhood of A is c times bigger than A, then the graph is called a c-expander.

Though many random graphs end up being expanders, expanders don’t have to be random. Rather, an expander “has the properties of a random graph without needing randomness,” said Tom Gur of the University of Cambridge.

Because of the conditions they must satisfy, expander graphs are highly interconnected, meaning you can get from one part of the graph to another in relatively few steps, even when there aren’t many edges. Expanders, Gur said, manifest the tension between connectivity and sparsity.

Early work on expander graphs was inspired by networks of neurons, and the graphs have shown up in other domains as well. Some large online social networks are expanders, and expanders can be used to build efficient error-correcting codes and improve the accuracy of random algorithms.

In their 2002 paper, Krivelevich and Sudakov proved that certain types of expanders have Hamiltonian cycles. They thought that expanders more generally also have such cycles, but they couldn’t prove it. “We firmly believed that the conjecture should be true, and we also pretty firmly believed that [proving] the conjecture would be very, very hard,” Krivelevich said.

Over the next two decades, Sudakov returned to the problem occasionally but didn’t make much progress. That changed in March 2023, when Sudakov, his student David Munhá Correia, and Stefan Glock of the University of Passau improved on the 2002 result, showing that a slightly larger class of expander graphs must have Hamiltonian cycles. “We generated many ideas and at some point realized that they can be combined in the right way,” Sudakov said. “David and Stefan were very enthusiastic about the problem all the time and not willing to give up.”

The following month, Richard Montgomery from the University of Warwick and Alexey Pokrovskiy of University College London came to visit Sudakov in Zurich. Montgomery had tried to prove Sudakov and Krivelevich’s conjecture as part of his doctorate at Cambridge in the early 2010s, but had given up because he thought he didn’t have the right tools to tackle the problem. With the recent progress made by Sudakov, Munhá Correia and Glock, Montgomery thought it was worth another attempt. “I suggested this to work on, without necessarily any strong sense that we would make any significant progress,” Montgomery said.

Over the next couple of weeks, Montgomery, Sudakov and Pokrovskiy came up with a strategy. They used a technique called Pósa rotation to amass a collection of long paths, hoping to eventually connect those paths into a Hamiltonian cycle. Montgomery returned home to Warwick without a proof, but with newfound optimism. “We had this feeling that eventually, one way or another, we should have the right ideas to get the result,” Sudakov said.

Near the end of 2023, Munhá Correia and a recently graduated student of Sudakov’s, Nemanja Draganić, told Sudakov that they had also been working on the conjecture. Munha Correia and Draganić had an idea for connecting paths into a Hamiltonian cycle using a contraption called a sorting network, which they’d come across in a November 2023 paper. “We sat together and realized that all these ideas could be put together to, probably, solve the problem,” Munhá Correia said.

A sorting network is a graph that contains two matching sets A and B. The sorting network is structured so that no matter how you pair points in A with points in B, it’s possible to find nonintersecting paths that connect each point in A with its corresponding point in B.  “You tell me how you enter, and you tell me how you want to exit,” Sudakov explained. “The sorting network has a property that there is a path from every vertex to the destination.”

The paper from November contained a proof that particular types of expander graphs must contain sorting networks. Draganić, Montgomery, Munha Correia, Pikrovskiy, and Sudakov realized that if they could combine sorting networks with Pósa rotation, they would be able to prove the conjecture. They used the techniques of the November 2023 paper to show that expander graphs also must contain sorting networks. Then, by taking the sets A and B to be the endpoints of the paths they’d created using Pósa rotation, they saw that they could tie their collection of long paths into a Hamiltonian cycle. “We crystallized all the key concepts which we need for the proof,” Sudakov said.

By February, the group had written up their paper. It proved not only the original 2002 conjecture of Krivelevich and Sudakov, which had used a narrower definition for expanders, but something even stronger: Any c-expander has a Hamiltonian cycle, as long as c is big enough. Their method also generated an actual Hamiltonian cycle, rather than proving abstractly that one existed. Sudakov forwarded the draft to Krivelevich. “I was rather doubtful we’d see it solved in our lifetime,” Krivelevich responded.

The new proof solves several questions about Hamiltonian cycles. It proves, for instance, that certain types of graphs that have to do with groups, called Cayley graphs, must have Hamiltonian cycles. But it isn’t the last word. Mathematicians could still try to find the lowest possible bound on c, the expansion factor, and perhaps prove that a broader class of graphs, called tough graphs, must contain cycles. (Sudakov said that though this is an aspiration, a proof is “nowhere close,” and he cautioned that “there is no good evidence that the conjecture is even true.”)

Gur, who wasn’t involved in the work, said it establishes “a fundamental connection between two objects which are central to computer science.” That connection, he said, will lead to important applications. “I don’t know what form it will take. It just seems like this is bound to be useful.”

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/in-highly-connected-networks-theres-always-a-loop-20240607/

Tags: Connectedhighlyscience
Previous Post

Can Psychedelics Improve Mental Health?

Next Post

Scotland v Finland

Rising stars: Young classical musicians surging on social media – Yahoo

Meet the Next Generation of Classical Music Sensations Making Waves on Social Media!

June 2, 2025
Medicaid work rules could leave a million Californians with no health insurance – CalMatters

California’s Medicaid Work Rules: A Million Residents at Risk of Losing Health Coverage!

June 2, 2025
Texas Democrat Beto O’Rourke returns to Houston area for another town hall – Houston Public Media

Beto O’Rourke Makes a Comeback: Join Him for an Engaging Town Hall in Houston!

June 2, 2025
In Indore, Alstom’s advanced metro train and CBTC signalling technology transform urban mobility as revenue service commences – Alstom

Revolutionizing Urban Mobility: Alstom Launches Advanced Metro Train and Cutting-Edge Signalling Technology in Indore

June 2, 2025
NFLPA says it’s not “actively preparing” for European division – NBC Sports

NFLPA Clarifies: No Plans for an NFL European Division Just Yet!

June 2, 2025
Conservation | Definition, Ecology, Examples, & Facts – Britannica

Unlocking the Secrets of Conservation: Understanding Ecology, Real-World Examples, and Fascinating Facts

June 2, 2025
Invisible radiation leaking from private satellite ‘megaconstellations’ could ruin radio astronomy forever, experts warn – Live Science

Invisible radiation leaking from private satellite ‘megaconstellations’ could ruin radio astronomy forever, experts warn – Live Science

June 2, 2025
Why a science-based climate policy helps business leaders – The World Economic Forum

Unlocking Success: How Science-Based Climate Policies Empower Business Leaders

June 2, 2025
Exercise boosts survival rates in colon cancer patients, study shows – The Lufkin Daily News

How Exercise Can Significantly Improve Survival Rates for Colon Cancer Patients

June 2, 2025
2025 Team USA U20 Wrestling World Team Set – FloWrestling

Meet the Future Stars: Team USA’s U20 Wrestling World Team for 2025 Unveiled!

June 2, 2025

Categories

Archives

June 2025
MTWTFSS
 1
2345678
9101112131415
16171819202122
23242526272829
30 
« May    
Earth-News.info

The Earth News is an independent English-language daily published Website from all around the World News

Browse by Category

  • Business (20,132)
  • Ecology (658)
  • Economy (672)
  • Entertainment (21,580)
  • General (15,256)
  • Health (9,716)
  • Lifestyle (675)
  • News (22,149)
  • People (674)
  • Politics (682)
  • Science (15,893)
  • Sports (21,178)
  • Technology (15,660)
  • World (660)

Recent News

Rising stars: Young classical musicians surging on social media – Yahoo

Meet the Next Generation of Classical Music Sensations Making Waves on Social Media!

June 2, 2025
Medicaid work rules could leave a million Californians with no health insurance – CalMatters

California’s Medicaid Work Rules: A Million Residents at Risk of Losing Health Coverage!

June 2, 2025
  • About
  • Advertise
  • Privacy & Policy
  • Contact

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

Go to mobile version