4 ms·
Mathematicians Build Long-Awaited Graph Sandwich
https://arxiv.org/abs/2510.20765 https://arxiv.org/abs/2510.20765
- NickNaraghi 20d agoSeems like this would have strong implications for distillation and/or smaller types of transformers!
- Scene_Cast2 20d agoHow? I don't see it. (I'm familiar with the ML side, not the combinatorics side.)
- emil-lp 20d agoNo, this is pure graph theory, and is quite far away from anything machine learning.
- mindleyhilner 20d agoActual meat: https://arxiv.org/abs/2510.20765 https://arxiv.org/abs/2510.20765
- emil-lp 20d agoIsn't it actually the bread? The meat is given, if I understand correctly.
- bananaflag 20d agoNice, it's pre-AI
- bhouston 20d agoI am not a mathematician but are most papers now accompanied by a lean proof? Is there a central repository of lean proofs shared by mathematicians like an npm repository of JavaScript packages? Does it all depend on a stupid is-odd package in the end?
- danabramov 20d agoIt's new but there is actually a registry now: https://palomar-registry.org/ https://palomar-registry.org/
- UltraSane 20d agoLLMs have gotten good at creating Lean proofs so the are much more common but not universal. And they depend on https://github.com/leanprover-community/mathlib4 https://github.com/leanprover-community/mathlib4
- emil-lp 20d agoNo, almost none (except for in certain fields, such as HoTT) have formalized proofs.
- bhouston 20d agoWhy not? It seems like this should sort of be the standard now? Or is it hard to make lean proofs in all fields?
- bbeonx 20d agoi think there are a few reasons. - lean proofs are hard, and a lot of the time there is so much mathematical machinery that folks are working on that you would need to not only prove your result, but also all of the machinery that your subfield it is built on. it would be infeasible for many authors to do all of this work (this might be a major part of multiple careers, and when there are 5 folks in your entire subfield, the payoff is not really worth it) - human proofs are readable, and can illustrate concepts better than lean proofs. human proofs give insights into how to think about a type of problem, and this is often the most valuable part of a proof/result. - lean proofs are often very difficult to read; while they give you a "verified" check mark, they do not necessarily improve the bounds of human understanding if that makes sense.
- bhouston 20d agoThank you for the response.
- Sniffnoy 20d agoWondering: if the process for the upper part of the sandwich is the complement of the process for the lower part, why was it so much more difficult? What would go wrong if you took one of the earlier lower-sandwich processes, and complemented it in a similar way? I have to assume it's something, but what?
- zem 20d agomy guess is that they also had to prove that the complement process was mathematically sound
- msupuka 17d agoWhat goes wrong is the accuracy guarantee. Complementing gives an upper graph, but the old guarantee doesn’t establish that it’s close enough to the target graph - which is what the theorem requires…
- omnicognate 20d agoHilarious - a mathematical result that afaict has nothing whatsoever to do with AI, and 75% of the comments are about AI, including this one!
- bbeonx 20d agolol yeah we're doomed
- upheaval7276 20d agoand this one edit: AI
- deleted 19d ago[deleted]
- deleted 20d ago[deleted]
- cryptolobster 20d agoGiven how much surrounding machinery the graph sandwich proof depends on, would it even be feasible to formalize it in Lean without first formalizing large chunks of random graph theory? And if not, does that mean results like this will stay out of reach for formal verification for the foreseeable future?
- minkowski 19d agoProbably not since LLMs can now carry out very large formalizations (https://www.anthropic.com/research/formalizing-fermats-last-theorem https://www.anthropic.com/research/formalizing-fermats-last-...).
- rbanffy 17d agoUnless humans understand them, can we trust such formalisations? We can prove the formalisation is correct, but we can't prove it accurately reflects what we are trying to prove.