• Latest
  • Trending
  • All
  • News
  • BUSINESS
  • SCIENCE
  • LIFESTYLE
  • TECH
Hypergraphs Reveal a Solution to a 50-Year-Old Problem

Hypergraphs Reveal a Solution to a 50-Year-Old Problem

August 1, 2022
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire

iSun Inc. Wins Two New Solar Projects Valued at $4.9 Million in Maine – Business Wire

March 29, 2023
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire

Redwire Corporation Reports Fourth Quarter and Full Year 2022 … – Business Wire

March 29, 2023
2023 McDonald’s All-American Boys Game: Photos and recap

2023 McDonald’s All-American Boys Game: Photos and recap

March 29, 2023
Kylie Jenner Rocks Crop Top & Leggings During Workout Routine: Video – Hollywood Life

Kylie Jenner Rocks Crop Top & Leggings During Workout Routine: Video – Hollywood Life

March 29, 2023
Tips To Cut Costs On Training Development

Tips To Cut Costs On Training Development

March 29, 2023
Target Announces Spring Designer Collection With RHODE, Fe Noel, and Agua Bendita – Target Spring Designer Collection 2023

Target Announces Spring Designer Collection With RHODE, Fe Noel, and Agua Bendita – Target Spring Designer Collection 2023

March 29, 2023
The BEST Twice Baked Potatoes

The BEST Twice Baked Potatoes

March 29, 2023
Vaccination Could Reduce Risk of Long COVID, Study Shows

Bias, Lack of Access Make Long COVID Worse for Patients of Color

March 29, 2023
Even in Ancient Times, Soldiers Wrote Messages on Ammunition

Even in Ancient Times, Soldiers Wrote Messages on Ammunition

March 29, 2023
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire

Ault Alliance’s Subsidiary, BitNile Inc., Collaborates with Core … – Business Wire

March 29, 2023
Religious attendance dips slightly after pandemic

Religious attendance dips slightly after pandemic

March 29, 2023
The King of Prussia Mall

The King of Prussia Mall

March 29, 2023
  • Home
  • News
    • PRESS RELEASE
  • Shop
  • BUSINESS
    • CRYPTO
    • ECONOMY
    • FINANCE
    • MARKET
    • MONEY
  • TECH
    • APPS
    • GADGET
    • MOBILE
    • SCIENCE
  • SOCIAL MEDIA
  • ENTERTAINMENT
    • ARTS & THEATER
    • GAMING
    • GAMBLING
    • MOVIE
    • MUSIC
    • SHOWS
    • SPORTS
  • LIFESTYLE
    • CELEBRITY
    • CULTURE
    • Education
    • FASHION
    • FOOD
    • HEALTH
    • HISTORY
    • Nature
    • Religion
    • Shopping
    • TRAVEL
  • REAL ESTATE
  • Blog
  • Classifieds
No Result
View All Result
No Result
View All Result
Home SCIENCE

Hypergraphs Reveal a Solution to a 50-Year-Old Problem

by Minnesota Digital News
August 1, 2022
in SCIENCE
0
Hypergraphs Reveal a Solution to a 50-Year-Old Problem
491
SHARES
1.4k
VIEWS
Share on FacebookShare on Twitter


The goal here is to trace out triangles on top of these lines such that the triangles satisfy two requirements: First, no two triangles share an edge. (Systems that fulfill this requirement are called Steiner triple systems.) And second, ensure that every small subset of triangles utilizes a sufficiently large number of nodes.

The way the researchers did this is perhaps best understood with an analogy.

Say that instead of making triangles out of edges, you’re building houses out of Lego bricks. The first few buildings you make are extravagant, with structural reinforcements and elaborate ornamentation. Once you’re done with these, set them aside. They’ll serve as an “absorber”—a kind of structured stockpile.

Now start making buildings out of your remaining bricks, proceeding without much planning. When your supply of Legos dwindles, you may find yourself with some stray bricks, or homes that are structurally unsound. But since the absorber buildings are so overdone and reinforced, you can pluck some bricks out here and there and use them without courting catastrophe.

In the case of the Steiner triple system, you’re trying to create triangles. Your absorber, in this case, is a carefully chosen collection of edges. If you find yourself unable to sort the rest of the system into triangles, you can use some of the edges that lead into the absorber. Then, when you’re done doing that, you break down the absorber itself into triangles.

Absorption doesn’t always work. But mathematicians have tinkered with the process, finding new ways to weasel around obstacles. For example, a powerful variant called iterative absorption divides the edges into a nested sequence of sets, so that each one acts as an absorber for the next biggest.

“Over the last decade or so there’s been massive improvements,” said Conlon. “It’s something of an art form, but they’ve really carried it up to the level of high art at this point.”

Erdős’ problem was tricky even with iterative absorption. “It became pretty clear pretty quickly why this problem had not been solved,” said Mehtaab Sawhney, one of the four researchers who solved it, along with Ashwin Sah, who like Sawhney is a graduate student at the Massachusetts Institute of Technology; Michael Simkin, a postdoctoral fellow at the Center of Mathematical Sciences and Applications at Harvard University; and Matthew Kwan, a mathematician at the Institute of Science and Technology Austria. “There were pretty interesting, pretty difficult technical tasks.”

For example, in other applications of iterative absorption, once you finish covering a set—either with triangles for Steiner triple systems, or with other structures for other problems—you can consider it dealt with and forget about it. Erdős’ conditions, however, prevented the four mathematicians from doing that. A problematic cluster of triangles could easily involve nodes from multiple absorber sets.

“A triangle you chose 500 steps ago, you need to somehow remember how to think about that,” said Sawhney.

What the four eventually figured out was that if they chose their triangles carefully, they could circumvent the need to keep track of every little thing. “What it’s better to do is to think about any small set of 100 triangles and guarantee that set of triangles is chosen with the correct probability,” said Sawhney.

The authors of the new paper are optimistic that their technique can be extended beyond this one problem. They have already applied their strategy to a problem about Latin squares, which are like a simplification of a sudoku puzzle.

Beyond that, there are several questions that may eventually yield to absorption methods, said Kwan. “There’s so many problems in combinatorics, especially in design theory, where random processes are a really powerful tool.” One such problem, the Ryser-Brualdi-Stein conjecture, is also about Latin squares and has awaited a solution since the 1960s.

Though absorption may need further development before it can fell that problem, it has come a long way since its inception, said Maya Stein, the deputy director of the Center for Mathematical Modeling at the University of Chile. “That’s something that’s really great to see, how these methods evolve.”

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.



Source link

Share196Tweet123Share49
Minnesota Digital News

Minnesota Digital News

Saint Paul
◉
12°
Sunny
6:58 am7:35 pm CDT
Feels like: 3°F
Wind: 7mph WNW
Humidity: 68%
Pressure: 30.45"Hg
UV index: 0
ThuFriSatSun
41/37°F
41/23°F
37/25°F
52/34°F
Weather forecast Saint Paul, Minnesota ▸
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire
PRESS RELEASE

iSun Inc. Wins Two New Solar Projects Valued at $4.9 Million in Maine – Business Wire

by Minnesota Digital News
March 29, 2023
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire
PRESS RELEASE

Redwire Corporation Reports Fourth Quarter and Full Year 2022 … – Business Wire

by Minnesota Digital News
March 29, 2023
2023 McDonald’s All-American Boys Game: Photos and recap
SPORTS

2023 McDonald’s All-American Boys Game: Photos and recap

by Minnesota Digital News
March 29, 2023
Kylie Jenner Rocks Crop Top & Leggings During Workout Routine: Video – Hollywood Life
CELEBRITY

Kylie Jenner Rocks Crop Top & Leggings During Workout Routine: Video – Hollywood Life

by Minnesota Digital News
March 29, 2023
Tips To Cut Costs On Training Development
Education

Tips To Cut Costs On Training Development

by Minnesota Digital News
March 29, 2023
Target Announces Spring Designer Collection With RHODE, Fe Noel, and Agua Bendita – Target Spring Designer Collection 2023
FASHION

Target Announces Spring Designer Collection With RHODE, Fe Noel, and Agua Bendita – Target Spring Designer Collection 2023

by Minnesota Digital News
March 29, 2023
The BEST Twice Baked Potatoes
FOOD

The BEST Twice Baked Potatoes

by Minnesota Digital News
March 29, 2023
Vaccination Could Reduce Risk of Long COVID, Study Shows
HEALTH

Bias, Lack of Access Make Long COVID Worse for Patients of Color

by Minnesota Digital News
March 29, 2023
Even in Ancient Times, Soldiers Wrote Messages on Ammunition
HISTORY

Even in Ancient Times, Soldiers Wrote Messages on Ammunition

by Minnesota Digital News
March 29, 2023
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire
PRESS RELEASE

Ault Alliance’s Subsidiary, BitNile Inc., Collaborates with Core … – Business Wire

by Minnesota Digital News
March 29, 2023
Religious attendance dips slightly after pandemic
Religion

Religious attendance dips slightly after pandemic

by Minnesota Digital News
March 29, 2023
The King of Prussia Mall
Shopping

The King of Prussia Mall

by Minnesota Digital News
March 29, 2023
Elon Musk and Steve Wozniak: pause more powerful A.I.
BUSINESS

Elon Musk and Steve Wozniak: pause more powerful A.I.

by Minnesota Digital News
March 29, 2023
Elon Musk and top AI researchers call for pause on ‘giant AI experiments’
TECH

Elon Musk and top AI researchers call for pause on ‘giant AI experiments’

by Minnesota Digital News
March 29, 2023
Amazon Has Thousands of Trendy Spring Skirts— These Are the 15 We Love
ENTERTAINMENT

Amazon Has Thousands of Trendy Spring Skirts— These Are the 15 We Love

by Minnesota Digital News
March 29, 2023
Making $100K in 18 Months with “Misfit” Medium-Term Rentals
REAL ESTATE

Making $100K in 18 Months with “Misfit” Medium-Term Rentals

by Minnesota Digital News
March 29, 2023
DOJ Appeals NAR Win In Probe Of Commission, Pocket Listing Rules
SCIENCE

DOJ Appeals NAR Win In Probe Of Commission, Pocket Listing Rules

by Minnesota Digital News
March 29, 2023
Over 100k Realme C55 units moved within 5 hours of its first sale in India
MOBILE

Over 100k Realme C55 units moved within 5 hours of its first sale in India

by Minnesota Digital News
March 29, 2023
Benson Hill Announces Preliminary Unaudited 2022 Results and … – Business Wire
PRESS RELEASE

Micron Technology, Inc. Reports Results for the Second Quarter of … – Micron Investor Relations

by Minnesota Digital News
March 29, 2023
Minnesota Digital News

Copyright © 2023 Minnesota Digital News

Navigate Site

  • Disclaimer
  • Privacy Policy
  • Copyright Notice
  • Anti Spam Policy
  • Medical Disclaimer
  • DMCA Compliance
  • Terms and Conditions
  • Social Media Disclaimer
  • Amazon Affiliate disclaimer

Follow Us

No Result
View All Result
  • Home
  • News
    • PRESS RELEASE
  • Shop
  • BUSINESS
    • CRYPTO
    • ECONOMY
    • FINANCE
    • MARKET
    • MONEY
  • TECH
    • APPS
    • GADGET
    • MOBILE
    • SCIENCE
  • SOCIAL MEDIA
  • ENTERTAINMENT
    • ARTS & THEATER
    • GAMING
    • GAMBLING
    • MOVIE
    • MUSIC
    • SHOWS
    • SPORTS
  • LIFESTYLE
    • CELEBRITY
    • CULTURE
    • Education
    • FASHION
    • FOOD
    • HEALTH
    • HISTORY
    • Nature
    • Religion
    • Shopping
    • TRAVEL
  • REAL ESTATE
  • Blog
  • Classifieds

Copyright © 2023 Minnesota Digital News