* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Monday, October 6, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Charlie Hunnam Reflects on Playing a Serial Killer in Monster: The Ed Gein Story – Yahoo

    Charlie Hunnam Reveals the Dark Challenges of Playing a Serial Killer in Monster: The Ed Gein Story

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

    Why Taylor Swift Name-Dropped Elizabeth Taylor in Her New Album – Yahoo

    Here’s Why Taylor Swift Dropped Elizabeth Taylor’s Name in Her New Album

    Al Roker Gives Olivia Dean an Unexpected ‘New Job’ on the ‘Today’ Show – Yahoo

    Al Roker Shocks Olivia Dean with an Exciting New Role on the ‘Today’ Show

    Books about the arts and some haunts for a Denton October – Denton Record-Chronicle

    Uncover Artistic Treasures and Spooky Adventures to Experience in Denton This October

  • 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
    Forget Cowbells. Cows Wear High-Tech Collars Now. – The New York Times

    Ditch the Cowbells: Discover the High-Tech Collars Transforming Cattle Care

    What the Recent Price Surge Means for Figure Technology Solutions After SEC Settlement – Yahoo Finance

    What the Recent Price Surge Reveals About Figure Technology Solutions Following SEC Settlement

    MAC Brings iPad Technology to Football Sidelines Across All 13 Member Schools – Sports Video Group

    MAC Brings iPad Technology to Football Sidelines Across All 13 Member Schools – Sports Video Group

    Technology Is Becoming More Important Than Humans In CX – No Jitter

    Technology Is Becoming More Important Than Humans In CX – No Jitter

    A Tech Expo Shows What China Can Make, but Not Who’ll Buy It All – The New York Times

    Inside China’s Tech Expo: Cutting-Edge Innovations Face Uncertain Demand

    Steampunk Metal Oval Technology Sense Sunglasses Personality Handmade Chain Multicolor Sunglasses UV400 – The San Joaquin Valley Sun

    Steampunk Metal Oval Sunglasses with Handmade Multicolor Chain – Bold UV400 Protection and Unique Style

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Charlie Hunnam Reflects on Playing a Serial Killer in Monster: The Ed Gein Story – Yahoo

    Charlie Hunnam Reveals the Dark Challenges of Playing a Serial Killer in Monster: The Ed Gein Story

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

    Why Taylor Swift Name-Dropped Elizabeth Taylor in Her New Album – Yahoo

    Here’s Why Taylor Swift Dropped Elizabeth Taylor’s Name in Her New Album

    Al Roker Gives Olivia Dean an Unexpected ‘New Job’ on the ‘Today’ Show – Yahoo

    Al Roker Shocks Olivia Dean with an Exciting New Role on the ‘Today’ Show

    Books about the arts and some haunts for a Denton October – Denton Record-Chronicle

    Uncover Artistic Treasures and Spooky Adventures to Experience in Denton This October

  • 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
    Forget Cowbells. Cows Wear High-Tech Collars Now. – The New York Times

    Ditch the Cowbells: Discover the High-Tech Collars Transforming Cattle Care

    What the Recent Price Surge Means for Figure Technology Solutions After SEC Settlement – Yahoo Finance

    What the Recent Price Surge Reveals About Figure Technology Solutions Following SEC Settlement

    MAC Brings iPad Technology to Football Sidelines Across All 13 Member Schools – Sports Video Group

    MAC Brings iPad Technology to Football Sidelines Across All 13 Member Schools – Sports Video Group

    Technology Is Becoming More Important Than Humans In CX – No Jitter

    Technology Is Becoming More Important Than Humans In CX – No Jitter

    A Tech Expo Shows What China Can Make, but Not Who’ll Buy It All – The New York Times

    Inside China’s Tech Expo: Cutting-Edge Innovations Face Uncertain Demand

    Steampunk Metal Oval Technology Sense Sunglasses Personality Handmade Chain Multicolor Sunglasses UV400 – The San Joaquin Valley Sun

    Steampunk Metal Oval Sunglasses with Handmade Multicolor Chain – Bold UV400 Protection and Unique Style

    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

Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

October 6, 2025
Republicans are holding Americans’ health care hostage — and lying about it – MSNBC News

How Republicans Are Holding Americans’ Health Care Hostage – and Deceiving the Public

October 6, 2025
Irish language: Naomi Long says politicians are playing out ‘culture war’ – BBC

Naomi Long Slams Politicians for Igniting a Divisive ‘Culture War’ Over the Irish Language

October 6, 2025
Air quality speed run – Washington State Department of Ecology (.gov)

Battling Pollution: Washington State’s Urgent Fight for Cleaner Air

October 6, 2025
Equity in science is a beautiful lie — and I’m done pretending – Nature

Equity in science is a beautiful lie — and I’m done pretending – Nature

October 6, 2025
Explore a bird database with 11,500 species – Popular Science

Explore an Incredible Bird Database Showcasing 11,500 Stunning Species

October 6, 2025
South Shore broker funded ‘extravagant lifestyle’ with $11.6 million taken from clients and colleagues, prosecutors say – Boston.com

South Shore broker funded ‘extravagant lifestyle’ with $11.6 million taken from clients and colleagues, prosecutors say – Boston.com

October 6, 2025
QRG Capital Management Inc. Purchases 9,519 Shares of Marvell Technology, Inc. $MRVL – MarketBeat

QRG Capital Management Takes Bold Step by Acquiring 9,519 Shares of Marvell Technology

October 6, 2025
Jaxson Dart, Cam Skattebo fumble away a Giant opportunity vs. Saints – Yahoo Sports

Jaxson Dart, Cam Skattebo fumble away a Giant opportunity vs. Saints – Yahoo Sports

October 6, 2025
‘The World Report’ of The Church of Jesus Christ of Latter-day Saints – KSL TV 5

Inside The World Report: Exploring the Impact of The Church of Jesus Christ of Latter-day Saints

October 6, 2025

Categories

Archives

October 2025
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  
« Sep    
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 (854)
  • Economy (874)
  • Entertainment (21,749)
  • General (17,444)
  • Health (9,917)
  • Lifestyle (887)
  • News (22,149)
  • People (876)
  • Politics (886)
  • Science (16,085)
  • Sports (21,375)
  • Technology (15,855)
  • World (857)

Recent News

Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

October 6, 2025
Republicans are holding Americans’ health care hostage — and lying about it – MSNBC News

How Republicans Are Holding Americans’ Health Care Hostage – and Deceiving the Public

October 6, 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