0xDE

I'm a computer scientist at the University of California, Irvine, interested in algorithms, data structures, discrete geometry, and graph theory.

Home page: https://www.ics.uci.edu/~eppstein/
Blog: https://11011110.github.io/blog/about/
Book: https://www.ics.uci.edu/~eppstein/forbidden/
Wikipedia: https://en.wikipedia.org/wiki/User:David_Eppstein

Public Key

npub1p5zwqctkgq05ck6cm8v2mn48q9zwssfns7ks533njxt6aac865ssnz4d3n

NIP-05 Address

11011110_at_mathstodon.xyz@momostr.pink

Profile Code

nprofile1qqsq6p8qv9myq86vtdvdnk9de6nsz38ggyec0tg2gceer9aw7ura2ggpz3mhxue69uhhyetvv9ujuerpd46hxtnfduqs6amnwvaz7tmwdaejumr0dsjqwlks

Publishing to

relay.damus.io

nos.lol

Author Public Key

npub1p5zwqctkgq05ck6cm8v2mn48q9zwssfns7ks533njxt6aac865ssnz4d3n

Show more details

Last Notes

2026-08-18 18:20:21 UTC

- reply

My guess would be \(2:\sqrt5:\sqrt5\) so that they have the same height as their width

2026-06-06 07:42:46 UTC

Another day, another journal editorial board mass resignation: this time from Springer's _Natural Language Semantics_, over publisher demands to increase article publication charge revenue by increasing their number of acceptances: https://www.openlibhums.org/news/943/, via https://retractionwatch.com/2026/06/05/natural-language-semantics-journal-editors-resign-launch-new-journal/
Instead the same editors are launching a new diamond open-access journal, _Semantics of Natural Languages_, through the Open Library of Humanities.

2026-04-21 02:04:15 UTC

- reply

It doesn't help that the entire section is unsourced, so you can't go back to the source and compare to try to figure out what they really meant.

2026-02-20 19:09:57 UTC

I recently posted about archive.today (also archive.is, archive.ph, archive.fo, archive.li, archive.md, and archive.vn) using its archive links to launch a ddos attack against a blogger they accused of doxing them: https://mathstodon.xyz/@11011110/116028203974257264
That attack triggered #Wikipedia (at least, the English part) to discuss banning archive.today links, and the ensuing discussion turned up evidence that (as part of the same dispute with the same blogger) archive.today had also tampered with its archived content to falsify certain names in old archived links: https://en.wikipedia.org/wiki/Wikipedia:Requests_for_comment/Archive.is_RFC_5#Evidence_of_altering_snapshots
This led to a quick close of the discussion and a consensus to remove all archive.today links from Wikipedia: https://en.wikipedia.org/wiki/Wikipedia:Archive.today_guidance
For the same reasons I have removed all archive.today links from my blog, where I had been occasionally using them as a convenient way to access paywalled content. I suggest that others remove their links as well, lest you unwittingly become part of additional ddos attacks and falsification.

2026-02-18 01:21:30 UTC

The circle packing theorem (https://en.wikipedia.org/wiki/Circle_packing_theorem): every planar graph can be represented by the tangencies of a system of non-overlapping circles.
This theorem was proved by Koebe in 1936, and popularized in the 1980s by Fields medalist William Thurston as a discrete analogue to conformal mapping and uniformization. Its Wikipedia article was created by Oded Schramm in 2008, not long before his untimely mountaineering death. In his own research, Schramm found deep analogies between random walks on circle packings and Brownian motion. My interests in circle packing relate to its use in drawing graphs, constructing polyhedra for given graphs, modeling soap bubble foams, and finding planar separators. And others have found even more varied applications from the study of discrete symmetry groups of hyperbolic space to methods for visualizing the functional areas of the human brain, spread out into a flattened map.
Now a Good Article on Wikipedia.

2026-02-07 21:51:24 UTC

The Lambek–Moser theorem is a bijective equivalence between two different-looking mathematical objects: partitions of the positive integers into two disjoint subsets, and pairs of almost-inverse monotone functions from positive integers to non-negative integers.
Real monotone functions are inverse when their graphs are mirror reflections across the diagonal line \(y=x\). We can define something like a graph for an integer function, a staircase curve whose lowest point above any integer on the \(x\)-axis gives the function value; then two integer functions are almost-inverse when these curves are mirror reflections. The attached image shows these two reflected staircase curves for the prime-counting function and its almost-inverse. This pair of functions corresponds to the partition of positive integers into prime and non-prime (composite or one).
By using this equivalence to go from functions to partitions and back, you can sometimes get amazing formulas for sequences of integers that you might not expect to have a formula at all. For instance, the \(n\)th number that is not a \(k\)th power (for integer \(k>1\)) has the formula:
\[n+\left\lfloor\sqrt[k]{n + \lfloor\sqrt[k]{n}\rfloor}\right\rfloor.\]
Now a Good Article on Wikipedia, https://en.wikipedia.org/wiki/Lambek%E2%80%93Moser_theorem
https://media.mathstodon.xyz/media_attachments/files/116/031/542/180/683/024/original/5cfc4853e62aa665.png

2026-01-30 06:40:56 UTC

Generative AI and Wikipedia editing: What we learned in 2025, https://wikiedu.org/blog/2026/01/29/generative-ai-and-wikipedia-editing-what-we-learned-in-2025/, from the Wiki Education project, which mainly interfaces Wikipedia with academic course projects involving editing Wikipedia. Their takeaway message: "Wikipedia editors should never copy and paste the output from generative AI chatbots like ChatGPT into Wikipedia articles."
In more detail, they used Pangram to detect AI-written content, then checked it by hand (finding very few false positives!). They found only a low rate of hallucinated sources. However, more concerningly, in more than 2/3 of the flagged articles, they found sourced sentences whose sources did not contain the information in the sentence. More strongly, "For most of the articles Pangram flagged as written by GenAI, nearly every cited sentence in the article failed verification." This also led to a high rate of wasted WikiEdu staff time cleaning up after the student-made AI additions ("far more time attempting to verify facts in AI-generated articles than if we’d simply done the research and writing ourselves").
Via https://en.wikipedia.org/w/index.php?title=Wikipedia_talk:WikiProject_AI_Cleanup&curid=75478538&diff=1335593937&oldid=1335593653

2026-01-21 17:30:40 UTC

- reply

You would like to say that all rational triangles have periodic paths (known) and extend these paths to a neighborhood of each rational triangle in the space of triangles, covering the whole space by neighborhoods. The problem with that argument is that some "unstable" paths do not extend to neighborhoods. For some rational triangles all periodic paths are unstable, and even worse some do not have neighborhoods that can be covered by finitely many distinct types of periodic path. This makes it difficult to prove anything for nearby triangles, and I get the impression these difficult-to-be-near triangles get more dense at larger obtuse angles.

2026-01-21 07:03:52 UTC

- reply

The explanation is that I rediscovered this old conversation while searching for material for a new Wikipedia article https://en.wikipedia.org/wiki/Triangular_billiards
It needs more figures, and while playing around with some possibilities (which I haven't fleshed out yet) I ran into a curious phenomenon: You might expect the angles of most irrational triangles to have rank two, meaning that (when measured in multiples of pi) they generate a vector space of rank two over the rationals. They can't have rank three because they sum to pi. But the first one I tried, the triangle with edge lengths 2,3,4, has only rank one, because its angles satisfy another unexpected relation: if \(\phi\) and \(psi\) are the sharpest and second-sharpest angles, then \(3\phi+2\phi=\pi\). This appears to be closely related to the existence of periodic billiards paths perpendicular to the long side of this triangle.

2026-01-20 08:18:32 UTC

- reply

In this context "rational" means that the angles are rational multiples of pi (or equivalently rational numbers of degrees)

2025-12-26 20:25:49 UTC

Quadratrix of Hippias, now a Good Article on Wikipedia: https://en.wikipedia.org/wiki/Quadratrix_of_Hippias
This is a curve swept out by the crossing point of two moving lines, one rotating and one translating. The ancient Greeks discovered that if you have a copy of this curve already, you can use it to trisect angles and construct a square with the area of a given circle, two classical geometry problems that are impossible with compass and straightedge alone. As I wrote on an earlier blog post, https://11011110.github.io/blog/2025/03/22/ancient-greek-mathematics.html, you can also see curves like this when you take a photo of a spinning airplane propellor using a camera with a rolling shutter:
https://media.mathstodon.xyz/media_attachments/files/115/787/734/164/308/135/original/03bac1f937b52aac.png

2025-12-16 00:48:28 UTC

- reply

Sadly, they are definitely not the same. The SF author is Michael Victor Capobianco; the mathematician is Michael F. Capobianco.

2025-12-14 07:42:59 UTC

New blog post: Regular link-irregular graphs, https://11011110.github.io/blog/2025/12/13/regular-link-irregular.html
In two recent works, Akbar Ali, Gary Chartrand, and Ping Zhang conjecture that there is no regular link-irregular graph. Here “regular” means all vertices have equal degrees and “link-irregular” means all vertices induce non-isomorphic neighborhoods. In support of this conjecture, they show that it is true for degrees three and four. However, the probabilistic method shows this to be false for sufficiently high degrees.

2025-11-29 21:34:43 UTC

It's not a good time to be a program chair of a major conference:
21% of the peer reviews at ICLR (a major annual machine learning conference) were discovered to be entirely written by AI, and "more than half contained signs of AI use". This appears to be in violation of ICLR's terms of conduct, which "prohibited AI use that would have breached the confidentiality of manuscripts". The ICLR chairs write that they are planning to penalize reviewers who did this by desk-rejecting the reviewers' submissions but they say nothing about what they are doing for authors whose submissions received these reviews.
Report in Nature, https://www.nature.com/articles/d41586-025-03506-6, https://archive.is/1cmjJ; details of analysis by Pangram, https://www.pangram.com/blog/pangram-predicts-21-of-iclr-reviews-are-ai-generated; response from ICLR program chairs, https://blog.iclr.cc/2025/11/19/iclr-2026-response-to-llm-generated-papers-and-reviews/; via https://lobste.rs/s/ww6cfs/major_ai_conference_flooded_with_peer

2025-11-26 04:29:18 UTC

- reply

That might work but I'd rather not annoy whichever staffer has to answer it

2025-11-26 01:37:06 UTC

It is graduate-school application season and that means filling out lots of web forms to submit recommendation letters to lots of schools. One thing I am noticing is that a significant fraction of these forms require a phone number from the recommender. It has been years since my university automatically provided and paid for an office phone number for all faculty members; we could still have a number if we paid for it using our own funds but I do not. I am not going to put my personal cell phone number on these forms (fortunately they tend to allow any nonblank alphanumeric input) and if anyone I didn't know called on it I would probably not answer. Nobody ever calls to verify graduate-school recommendation letters anyway. So what is the point?

2025-11-23 07:09:51 UTC

- reply

I'm sure it's just normal TeX but running in a mode where they keep running after a lot of things that would interrupt a default TeX install

2025-11-22 23:35:02 UTC

- reply

In general Overleaf seems to have a setup with high resilience to problematic LaTeX sources, so that things work there that would not work elsewhere. It can cause problems of interoperability with other LaTeX systems because the Overleaf users learn to ignore any errors and warnings and write code that works only on Overleaf.

2025-11-19 16:22:35 UTC

- reply

braid meaning "broad" in Scots?

2025-11-19 06:36:36 UTC

- reply

Faces may be irrelevant for this example but they're just as easy to describe, as bitstrings with wildcards. Vertices (0-faces) are strings of five bits. Edges (1-faces) are strings with one of the bits replaced by a *. Squares (2-faces) are strings with two of the bits replaced by *s, etc. The vertices in a face are all ways of expanding each * into a 0 or 1.

2025-11-16 21:08:28 UTC

In a discussion on Wikipedia, I asserted that it is typical to group the operations within mathematical formulas into meaningful chunks, analogously to the way we group sequences of sounds or letters into meaningful words. The example I was looking at concerned covering the edges of a random graph \(G(n,\tfrac12)\) by few cliques, for which the number of cliques needed turns out to be \[\Theta\left(\frac{n^2}{\log^2 n}\right).\]
How I would expect such a formula to be read by someone knowledgeable about random graphs and the relevant notation is:
\(\Theta\): this is both an upper and a lower bound, and we are allowing ourselves to be sloppy about constant factors
\(n^2\): the number of edges in the graph
\(/\log^2 n\): smaller by a \(\log^2\) factor. But why \(\log^2\)? (After more thought, or looking a little farther into the source:) It's the number of edges that can be covered by a single clique.
It occurred to me to wonder: is this sort of chunking actually a typical way to read mathematical expressions? Where, if anywhere, do we teach beginning mathematicians to do this? Or is it just something they pick up along the way, maybe by example from seeing instructors talk about formulas, the way new language learners might pick up the ability to pick out and understand words from speech without ever being taught phonics?

2025-11-14 06:05:21 UTC

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs: https://arxiv.org/abs/2511.09707
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov, Vaishali Surianarayanan
New preprint, awarded best paper at the SIAM Symposium on Simplicity in Algorithms to be held next January in Vancouver. Does what it says in the title, solving a problem left unresolved after work in the early 1990s claimed to find a polynomial time algorithm but without detail and with methods later shown not to work.

2025-11-04 08:52:06 UTC

My university is threatening impending doom for course materials or online content that does not pass some unspecified accessibility check. All my course materials are formatted in LaTeX/beamer. If accessibility is defined as "images have alt text", then I know how to define alt text as a parameter to the includegraphics macro, but I strongly suspect it is getting dropped on the floor rather than included in the generated pdf. If accessibility is defined as "passes all Acrobat accessibility checks" then I am even more at sea.
I do want my materials to be accessible but I done little about this so far because without further guidance this seems an impossible demand, like that I suddenly rewrite all my content in Xhosa (or if you happen to actually know Xhosa, substitute a language unrelated to yours that you have no knowledge of). And I have no expectation that my campus accessibility people will or can provide any help.
So, does anyone here have any experience actually producing accessible documents with pdflatex and beamer? Preferably a solution that
- Works with pdflatex rather than some other custom LaTeX
- Works with common documentclasses including beamer
- Works with the external systems I am required to interoperate with via LaTeX including arXiv, LIPIcs, Overleaf, and who knows what else (this probably means pdflatex only, and that the first line of the source is the documentclass)
- Doesn't require me to update TeXLive from 2024 to 2025 breaking cleveref
- Generates pdf that both passes the Acrobat tests and actually improves accessibility (not the same thing as each other)
If so, can you point me to an online guide I can follow to do the same?

2025-10-22 05:53:00 UTC

New blog post, Hamiltonian-paired graphs, https://11011110.github.io/blog/2025/10/21/hamiltonian-paired-graphs.html, on the 4-regular graphs with the following property: every Hamiltonian cycle is complementary to another Hamiltonian cycle.
And new preprint, Hamiltonian cycles in subdivided doubles, http://arxiv.org/abs/2510.18359, on one method for constructing graphs with these property.
My initial motivation for all this was to understand why the Folkman graph has this property, and I think the preprint provides a good explanation. But figuring this out sent me down a rabbit hole of finding other graphs that have the same property, and the blog post describes two more constructions.

2025-09-30 23:10:10 UTC

A new proof smooths out the math of melting (https://www.quantamagazine.org/a-new-proof-smooths-out-the-math-of-melting-20250331/): Quanta on "On the multiplicity one conjecture for mean curvature flows of surfaces", https://arxiv.org/abs/2312.02106, by Bamler and Kleiner.
Imagine melting a cylindrical piece of ice (like you get at many US restaurants). At some point melting will likely break through the cylinder, producing a crescent shape with two sharp points that gradually smooth as the ice continues to melt. That topology change is a singularity, where something discontinuous happens to the ice surface. If you somehow managed to keep your ice toroidal, the point when it becomes an infinitesimally thin ring and then vanishes would be a more complicated singularity.
Modeling continuously changing surfaces requires understanding their singularities. This paper is on a specific type of surface evolution called mean curvature flow (https://en.wikipedia.org/wiki/Mean_curvature_flow), and shows that its unavoidable singularities have only a few simple forms: like the kind where you break through a torus to produce two sharp points, unlike the kind where an infinitesimally thin ring vanishes or worse.
This is the same general area as the proof of the geometrization and Poincaré conjectures using Ricci flow. One difference is that mean curvature flow depends on how the given 2d surface is embedded in 3d; Ricci flow depends only on the intrinsic geometry of a surface, and not its embedding. Another difference is that this new work is on 2d surfaces, but the geometrization and Poincaré conjectures look one dimension higher, at 3d hypersurfaces. You can also look one dimension lower, at curves in the plane, where the mean curvature flow becomes the curve-shortening flow (https://en.wikipedia.org/wiki/Curve-shortening_flow).

2025-09-28 22:14:42 UTC

- reply

https://www.youtube.com/watch?v=3cI-LXMyyDo

2025-09-19 22:44:41 UTC

Why you should be happy that you can use sin and cos in your web stylesheets even though the State of CSS 2025 results listed them as "most hated feature": https://css-tricks.com/the-most-hated-css-feature-cos-and-sin/ via https://news.ycombinator.com/item?id=45267336

2025-09-15 01:29:42 UTC

New blog post, Planarizing matchings, https://11011110.github.io/blog/2025/09/14/planarizing-matching.html, and new(ish) preprint, String graph obstacles of high girth and of bounded degree, https://arxiv.org/abs/2509.00278, with Maria Chudnovsky and David Fischer, to appear at Graph Drawing.
The image below shows the Petersen graph, with the three edges highlighted in yellow forming a planarizing matching: if you contract these three edges, the resulting 7-vertex graph is planar.
https://media.mathstodon.xyz/media_attachments/files/115/205/713/486/595/812/original/f57da238765a61a1.png

2025-08-14 04:10:45 UTC

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths: https://arxiv.org/abs/2504.17033, as discussed by Quanta in https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/ and published at STOC 2025 (https://dl.acm.org/doi/pdf/10.1145/3717823.3718179)
The new time bound, \(O(m\log^{2/3} n\), is faster than Dijkstra's \(m+n\log n\) for sparse enough graphs, meaning \(m=o(n\log^{1/3} n)\).

2025-08-11 20:24:29 UTC

You probably know about the five Platonic solids, convex polyhedra that are fundamental for point symmetries. But did you know there is a different set of five convex polyhedra, the parallelohedra, that are just as fundamental for translational symmetries? https://en.wikipedia.org/wiki/Parallelohedron, another new Good Article on Wikipedia.

2025-08-10 17:38:33 UTC

- reply

The code for generating these in OEIS looks slow and bad, but if you have a streaming generator for the usual primes, then the Fermi–Dirac primes are easy to generate in sorted order: just merge the primes and the squares of the generated Fermi–Dirac primes.

2025-08-08 07:13:16 UTC

Lysenkoism here we come: Trump puts all federal research grants under political rather than scientific control. https://arstechnica.com/science/2025/08/new-executive-order-puts-all-grants-under-political-control/

2025-08-06 22:48:08 UTC

The snake-in-the-box problem: not what I expected to see on xkcd today. https://xkcd.com/3125/

2025-07-08 04:53:55 UTC

New blog post "Ready lists", https://11011110.github.io/blog/2025/07/07/ready-lists.html and new arXiv preprint "Decremental Greedy Polygons and Polyhedra Without Sharp Angles", https://arxiv.org/abs/2507.04538
By a ready list, I mean a data structure like a stack or queue that collects newly added items and then gives them back to you one at a time, but where you don't care what order you get them back in. Surprisingly many basic algorithms can work with these in place of anything more constrained; the theory behind why they work involves antimatroids.
The preprint is on using this idea to solve an abstract optimization problem of finding subsets maximizing the minimum quality of any element, where the quality of an element within a subset decreases or stays the same when you remove other elements. To make this more concrete, the attached image shows an example: finding a polygon in a set of points whose sharpest angle is as large as possible.
https://media.mathstodon.xyz/media_attachments/files/114/815/801/519/179/330/original/bb665773b5c3704c.png

2025-06-28 00:35:41 UTC

- reply

My campus instituted a mandatory spyware program (without which one cannot access certain internal systems like the one for reimbursements) leading me to buy a cheap burner machine to run the spyware on. Bonus: I can do my mandatory training sessions on the burner while I multitask on my real office computer.

2025-06-09 15:29:01 UTC

I just had to take my name off a manuscript (not yet public) because it turned out that one of the coauthors had been using ChatGPT to help them write it all along without telling the rest of us and I don't want my name on that.
It didn't help that the same day I had to remove over 50% of a long Wikipedia article on algorithms because for months some editor had been using an LLM to expand it, complete with falsified references whose links went to actual papers on unrelated topics.

2025-05-21 07:02:07 UTC

My newest blog post "Bandwidth vs breadth-first search", https://11011110.github.io/blog/2025/05/20/bandwidth-vs-bfs.html, summarizes the results from my newest arXiv preprint, "Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing", https://arxiv.org/abs/2505.10789, with Mike Goodrich and his student Alfred Liu.
As the post begins, the new result started with a mistake. Finding an counterexample to this mistake, generalizing the counterexample, and then using the structure of the generalized counterexample as the basis for a proof that it was close to being the worst case for our problem, led us to the results that we ended up including in the preprint.

2025-04-26 02:34:15 UTC

Wikipedia’s nonprofit status questioned by Trump-appointed US attorney, accusing it of "allowing foreign actors to manipulate information": https://www.washingtonpost.com/technology/2025/04/25/wikipedia-nonprofit-ed-martin-letter/, https://archive.is/UNXVy, via https://news.ycombinator.com/item?id=43799302
Well, yes. Wikipedia editing is not limited to US-based Trump-loyalist propagandists. That's a good thing. This should be a warning, though, that Wikipedia's ownership and internet hosting being based in the US has become a liability rather than a strength.
See also _The Verge_, "Trump DOJ goon threatens Wikipedia", https://www.theverge.com/news/656720/ed-martin-dc-attorney-wikipedia-nonprofit-threat, _The Guardian_, "Why is Elon Musk attacking Wikipedia? Because its very existence offends him", from October 2023, _Le Monde_, "Why Elon Musk is calling for a boycott of Wikipedia", https://www.lemonde.fr/en/pixels/article/2025/01/29/why-elon-musk-is-calling-for-a-boycott-of-wikipedia_6737574_13.html, from January, and _The New Yorker_, "Elon Musk Also Has a Problem with Wikipedia: Lately, Musk’s beef has merged with a general conviction on the right that the site is biased against conservatives", https://www.newyorker.com/news/the-lede/elon-musk-also-has-a-problem-with-wikipedia, from March.

2025-04-07 20:30:34 UTC

- reply

Also relevant: https://axbom.com/dont-fake-bold-and-italic-text-with-unicode/
At least I assume that's what the illegible boxes between "new journal of mathematical logic that's" and "This means simply" were intended to be.

2025-04-07 16:52:36 UTC

- reply

Small correction: the journal is called "Zeitschrift für Mathematische Logik und Grundlagen der Mathematik". Still easier to abbreviate as ZML. The "Deutsche Vereinigung für Mathematische Logik und für Grundlagenforschung der Exakten Wissenschaften" is not the name of the journal, but the name of the society that sponsored the old journal and cancelled their sponsorship.

2025-03-11 23:42:07 UTC

- reply

If the choice is between the Scylla of Musk destroying the US Federal Government leaving the states to govern themselves, and the Charybdis of Trump turning the US into a nightmare repeat Nazi dictatorship and then maybe stumbling into a nuclear war with some random country he develops an irrational hatred of, then I think there is a clear lesser of two evils.

2025-03-04 03:35:50 UTC

If not all rounded triangles are Reuleaux triangles, it stands to reason that not all rounded tetrahedra are Reuleaux tetrahedra (the intersections of four spheres each centered at a point where the other three cross). Here's another one: the elliptope, the space of positive semi-definite matrices with unit diagonal, https://franknielsen.github.io/elliptope/index.html — for 3x3 matrices, there are three off-diagonal terms and you get a three-dimensional curved tetrahedron sitting inside a unit cube. It's a special case of a spectrahedron (https://en.wikipedia.org/wiki/Spectrahedron).
Via https://web-cdn.bsky.app/profile/bbolker.bsky.social/post/3lakemxuvf22z where the image makes clear that it is has a quite different geometry than the Reuleaux tetrahedron: the four tetrahedral faces meet at the straight line-segment edges of a regular tetrahedron, and pillow outward from there. Instead the Reuleaux tetrahedron's edges are circular arcs where two spheres meet.

2025-02-25 06:35:47 UTC

New blog post "Blooming caterpillars" (https://11011110.github.io/blog/2025/02/24/blooming-caterpillars.html), on a class of polyhedral nets that can be continuously unfolded from the cut surface of a convex polyhedron into a flat polygon, using a physical analogy involving countdown dice.

2025-02-10 17:53:03 UTC

- reply

Colorless green quarks sleep furiously (in a composite with their red and blue quarks).

2025-02-08 02:07:21 UTC

- reply

An actually useful post from this thread! All this time I've been using option-e e. Which works when I know the option-code, but this gets me more.

2025-01-24 08:55:31 UTC

What do all those different squiggly equal signs mean?
A Wikipedia discussion on the symbol \(\simeq\) (called "asymptotically equal to" by the Unicode consortium, unicode U+2243) led me to https://math.stackexchange.com/questions/864606/difference-between-%E2%89%88-%E2%89%83-and-%E2%89%85 where I learn that it is commonly used for homotopy equivalence or maybe equivalence of categories. In my experience the more common symbol for asymptotic equivalence is \(\sim\). It's unfortunate that Unicode named these by a specific (and in this case dubious) choice of semantics than by a name that could convey a wider meaning. I guess the LaTeX name "simeq" also conveys the idea of a meaning "similar or equal" but "similar" can mean a lot of things.
The stackexchange link also discusses several other such symbols.

2025-01-10 05:59:26 UTC

- reply

: @npub1kr6…lhf0 might tell you that behind the back is not a seam but an anholonomy such that you could walk around and around the tractroid, never see a seam, but also not return to the same space you started walking from.
It's hard to visualize, but I think also the more times you walk around the more the fish would appear to be spiraling around the tractroid rather than just being pulled straight up.

2025-01-08 05:36:12 UTC

Recent encounters with atom-thin salami slicing (https://reeserichardson.blog/2024/12/30/recent-encounters-with-atom-thin-salami-slicing/), several case studies in bad-to-dishonest academic publishing by Reese Richardson, via https://retractionwatch.com/2025/01/04/weekend-reads-honest-overachievers-the-unpublished-lucy-letby-paper-atom-thin-salami-slicing/

2024-12-28 22:42:16 UTC

- reply

something about the nature of the position turns the academics who take over into more bureaucrats. Or maybe the ones who take those positions are already budding bureaucrats.

2024-12-27 17:03:00 UTC

Buried in a story about yet another Elsevier journal editorial board resigning en masse (Journal of Human Evolution, https://retractionwatch.com/2024/12/27/evolution-journal-editors-resign-en-masse-to-protest-elsevier-changes/), there is an alarming new development in Elsevier's publication practices:
"In fall of 2023, for example, without consulting or informing the editors, Elsevier initiated the use of AI during production, creating article proofs devoid of capitalization of all proper nouns (e.g., formally recognized epochs, site names, countries, cities, genera, etc.) as well italics for genera and species. These AI changes reversed the accepted versions of papers that had already been properly formatted by the handling editors. This was highly embarrassing for the journal and resolution took six months and was achieved only through the persistent efforts of the editors. AI processing continues to be used and regularly reformats submitted manuscripts to change meaning and formatting and require extensive author and editor oversight during proof stage."

2024-12-20 17:35:34 UTC

- reply

The two goals are a little contradictory: the new mathematics Wikipedia editors are the ones who tend most to write for themselves rather than for a general audience. But they also tend to get better over time.

2024-12-20 01:22:01 UTC

I have a new paper _Princ-wiki-a Mathematica_: Wikipedia Editing and Mathematics, https://www.ams.org/journals/notices/202501/noti3096/noti3096.html, in the January _Notices of the AMS_, and a new blog post, Pseudonymity in academic publishing, https://11011110.github.io/blog/2024/12/19/pseudonymity-academic-publishing.html
The _Notices_ paper is on editing mathematics on Wikipedia, and I hope it encourages more to do so. The blog post is on the fact that the AMS would not let us list our pseudonymous coauthor as an author. Pseudonymity is important and highly protected on Wikipedia, in part because Wikipedia editing can sometimes put its editors into serious danger, but in this case it clashed with academic publishing standards, or at least the AMS's publishing policies, and I wanted to explore that.
Some of the other material in this issue also looked interesting to me, especially @npub1gve…sduy's article on machine-assisted proof (https://www.ams.org/cgi-bin/notices/nxgnotices.pl?next=202501) and Nick Trefethen's on rational approximation (https://www.ams.org/journals/notices/202501/noti3066/noti3066.html). See https://www.ams.org/cgi-bin/notices/nxgnotices.pl?next=202501 for the whole issue.

2024-12-17 18:03:05 UTC

- reply

There are some other differences than symmetry between your version and this one. Yours has three half-twists rather than one, and in the limit of rollers whose radius and distance from each other gets as small as possible (for a fixed belt width) its limiting form is a hexagon, because the three belts cannot simultanously overlap in the center. In this form, instead, there is only one half-twist, and a limiting form that is a smaller equilateral triangle, making the shortest possible flat rectangular Möbius band of a given width (see Schwarz, https://arxiv.org/abs/2308.12641).

2024-12-17 04:59:33 UTC

- reply

It's pretty easy to make a flat Möbius strip in 3d with three horizontal strips on three different horizontal planes, connected by cylindrical rollers.
In this schematic top-down projected view, the centerline can be any triangle, the rollers are perpendicular to the angle bisectors, and the diameter of each roller is the distance between two of the three horizontal planes. The actual geometry would be slightly different (the projected outline of the belt would curve as it passes around each roller) but not in a way that prevents the surface from being constructed like this.
https://media.mathstodon.xyz/media_attachments/files/113/666/371/063/884/444/original/05fd75223ea3a74c.png

2024-12-13 18:46:15 UTC

New Zealand halves its funding for basic research and cuts all such funding in social science and humanities: https://www.science.org/content/article/amid-cuts-basic-research-new-zealand-scraps-all-support-social-sciences, via https://news.ycombinator.com/item?id=42405956

2024-12-03 08:04:06 UTC

- reply

Re higher dimensional extensions of Pick: one obstacle is the Reeve tetrahedra (https://en.wikipedia.org/wiki/Reeve_tetrahedra), which have different volumes but look the same as each other with respect to counting interior and boundary lattice points.

2024-12-03 05:29:41 UTC

- reply

Isn't it the same for any lattice? Area = (Pick formula) * fundamental parallelogram area = (Pick formula) * 2 * (triangle area)

2024-11-24 08:39:43 UTC

For-profit academic publishers love LLM garbage: Kevin Munger on Crooked Timber, https://crookedtimber.org/2024/11/08/for-profit-academic-publishers-love-llm-garbage/
Munger argues that under current open-access pay-to-publish standards, they make a profit on each LLM-produced paper, are motivated primarily by profit, and have little short-term incentive to make their journal content meaningful to subscribers. Therefore, if we want to continue to be able to find meaningful scholarly content, we need to look elsewhere than these publishers. Munger advocates diamond open-access instead, cutting out the profit motive.

2024-11-13 08:15:27 UTC

- reply

A fox for every henhouse

2024-11-12 02:33:39 UTC

Lower bounds for adaptive relaxation-based algorithms for single-source shortest paths: https://arxiv.org/abs/2411.06546, by Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, and Marek Chrobak, to appear at ISAAC 2024.
This is part of a line of work including a paper of mine at WADS 2023 (see https://11011110.github.io/blog/2023/05/17/permutation-supersequences-shortest.html and https://arxiv.org/abs/2305.09230) where I proved that, among shortest-path algorithms that perform relaxation steps in a fixed order, depending on the graph but not on the results of previous steps, Bellman-Ford is within a constant factor of the optimal number of steps. In https://arxiv.org/abs/2402.10343, Jialu Hu and László Kozma eliminated the constant factor for deterministic algorithms on complete graphs, as a result showing that an older paper of mine, on a randomized version of Bellman–Ford (https://11011110.github.io/blog/2011/04/11/randomized-bellmanford.html and https://arxiv.org/abs/1111.5414) is strictly better than deterministic for this case. The new paper extends these results in a different direction, to algorithms whose order of operations depends (in a restricted way) on the results of previous operations, as you would want to do in any practical implementation of Bellman–Ford. For instance, once an edge has been relaxed, there's no point in doing it again until some other step has caused the distance to its starting vertex to improve.
If you want to see this at ISAAC, in Sydney, Australia, December 8–11, you need to preregister! Registration is open only until November 29, and will not be available at the conference. See https://sites.google.com/view/isaac2024/registration (via https://kamathematics.wordpress.com/2024/11/11/guest-post-isaac24-in-sydney-registration-deadline-soon/). And for the full list of ISAAC papers, see https://sites.google.com/view/isaac2024/list-of-accepted-papers

2024-11-04 19:03:43 UTC

- reply

My guess: they are terrified of security breaches that open them up to ransomware attacks and somehow got the idea that web content that they do not directly control is a security hazard.

2024-11-04 17:37:24 UTC

- reply

A high-profile web page of a professor at a university brings credit to the university itself. On the other hand, for the personal web page you link, you have to go to the separate about page and read through to the second paragraph of fine print before even finding out where they work. It seems counterproductive for a university to want to anonymize itself in this way.

2024-11-03 16:33:27 UTC

- reply

They say that 1 hexagon is impossible. The reference for this in the Wikipedia fullerene article is Meija, Juris (2006). "Goldberg Variations Challenge" (PDF). Analytical and Bioanalytical Chemistry. 385 (1): 6–7. doi:10.1007/s00216-006-0358-9. PMID 16598460. S2CID 95413107. See also https://oeis.org/A007894 and note the 0 in the second position. There must be a mathematical rather than chemical explanation somewhere but I don't know where to find it.

2024-11-02 06:44:38 UTC

- reply

Find any vertex-to-vertex line segment in the triangle grid that crosses the small equilateral triangles in any way that you like, rotate it by 60° to make an equilateral triangle, and make a regular icosahedron out of these triangles. The edges (fold lines) of this icosahedron will all cross the small equilateral triangles in the same way.

2024-10-31 04:15:17 UTC

A lower bound for the quickhull convex hull algorithm that disproves the quickhull precision conjecture: Mike Goodrich, https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4989035
Mike tells me that he didn't actually intend to post this as a preprint on ssrn but must have clicked the wrong button trying to submit it to an Elsevier journal. But I think that making it public in this way, even accidentally, is relatively harmless, this time.
Oh, the result? It's about quickhull (https://en.wikipedia.org/wiki/Quickhull), an algorithm for 2d convex hulls. It is known that
- Quickhull on worst-case inputs with unbounded coordinates takes \(O(n^2)\) time, and no better bound is possible.
- Quickhull on random points in a convex region takes \(O(n)\) expected time.
- Quickhull on points with integer coordinates of polynomial size takes \(O(n\log n)\) time.
- Quickhull on inputs whose hull has \(h\) edges takes \(O(nh)\) time.
There was a conjecture from 1996 that the last two of these bounds could be combined: that quickhull on points with integer coordinates of polynomial size and \(h\) hull edges takes \(O(n\log h)\) time. The conjecture is wrong.
Quickhull is a divide-and-conquer algorithm that recursively partitions its input at the midpoint of its range of \(x\)-coordinates. The optimality of \(O(n^2)\) can be shown using \(n\) points with coordinates \((2^i,3^i)\), causing these splits to be highly uneven. The new counterexample is the same construction with \(h\) points, for \(h\) small enough to produce polynomially-large coordinates, plus \(n-h\) points that get carried along for the ride through \(h\) levels of recursion. This shows that \(O(nh)\) is optimal for small-enough \(h\).

2024-10-28 22:13:07 UTC

- reply

But by Alexandria again, a sphere with cone points is exactly equivalent to a unique polyhedron. See Alexandriv's uniqueness theorem on Wikipedia.

2024-10-28 13:25:02 UTC

- reply

As I said elsewhere in this thread, this is known separately from Thurston as the star unfolding: https://en.wikipedia.org/wiki/Star_unfolding
It was used by Alexandrov well before Thurston. You can define it for any convex polyhedron.

2024-10-26 18:25:49 UTC

- reply

Now that I looked through Thurston's paper, I see that his construction is just the star unfolding from one of the vertices of the polyhedron (see https://en.wikipedia.org/wiki/Star_unfolding). That sort-of-explains the cursed shape of the yellow net: "Despite their names, the source unfolding always produces a star-shaped polygon, but the star unfolding does not."
So the construction definitely can produce non-convex outer 11-gons (because if you start with a non-convex outer 11-gon such as the one in my post, and then repeat the construction with the same choice of star vertex, you will get the same net back again). I don't know whether there exist polyhedra for which all 12 choices of star vertex produce non-convex outer 11-gons but I wouldn't be surprised if that were true.
Pinging @npub1nrj…kuk3 as a devotee of polyhedral nets and unfoldings

2024-10-26 07:29:12 UTC

- reply

Cute. But there appears to be a missing constraint in the description of how to do this: the green triangles need to be separated from each other in order to make the yellow net be a simple polygon. That is not true for all 11-gons. Also, your drawing shows a convex 11-gon, but that is not necessary; the same procedure can work for non-convex 11-gons (I don't know whether the proof that all polyhedra of this type can be represented in this way requires non-convexity).
https://media.mathstodon.xyz/media_attachments/files/113/372/541/416/673/757/original/de28ee9aac1cd9db.png

2024-10-20 07:32:44 UTC

Pentagonal bipyramids lead to the smallest flexible embedded polyhedron: https://arxiv.org/abs/2410.13811, new preprint by
Matteo Gallet, Georg Grasegger, Jan Legerský, and Josef Schicho
Convex polyhedra are rigid, but some special non-convex polyhedra have at least one continuous degree of freedom. (More than one degree of freedom can be obtained in a trivial way by gluing such polyhedra.) The Bricard octahedra (https://en.wikipedia.org/wiki/Bricard_octahedron) have the same combinatorial structure as a regular octahedron, and can sort of flex, but only if you allow faces that can cross through each other. You can avoid the crossings, for instance by making little gussets near where they would happen, at the expense of making the shape more complicated.
It was believed that Steffen's polyhedron, with 9 vertices, 21 edges, and 14 triangular faces, was the simplest possible non-self-intersecting flexible polyhedron. For instance, Demaine and O'Rourke's book _Geometric Folding Algorithms_ (p. 347) writes "As it was later proven that all triangulated polyhedra of eight vertices are rigid, Steffen’s example is minimal in this sense."
But it was apparently not proven, and the new preprint claims a better example: an 8-vertex polyhedron formed from a pentagonal bipyramid by subdividing one triangle into three. This seems a bizarre choice because this subdivision does not affect flexibility. But it can act as a gusset pulling two parts of the boundary away from each other, changing a self-crossing bipyramid into a non-self-crossing subdivided bipyramid.

2024-10-18 04:22:27 UTC

New blog post: Splines for graph drawing theory, https://11011110.github.io/blog/2024/10/17/spline-graph-drawing.html
Related new arXiv preprint: Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature (with Mike Goodrich and Abraham Illickan), https://arxiv.org/abs/2410.12083

2024-10-17 01:30:08 UTC

- reply

Typo: Nima, not Nina

2024-10-15 23:26:50 UTC

I'm sure many have seen https://stallman-report.org/ detailing Richard Stallman's misconduct and how it and his enablers have harmed the free software movement. Much of this is not new but I was still shocked by a line early in the "Why publish this report?" section: "Women represent just 3% of the free software community, compared to 23% of industry programmers generally." Obviously not all of that disparity can be attributed to #Stallman alone, but his continued position of prominence is a symptom of a broader disease in the community's culture. Paying attention to these problems rather than turning a blind eye to them is a necessary step towards healing.

2024-10-07 00:52:15 UTC

New blog post: a half-flipped binary tiling, https://11011110.github.io/blog/2024/10/06/half-flipped-binary.html
Mostly an excuse to show and explain the following image:
https://media.mathstodon.xyz/media_attachments/files/113/263/386/426/684/610/original/e1524ee94a3f12ef.png

2024-10-01 22:25:23 UTC

- reply

What, no mention of one of the most famous examples? https://en.wikipedia.org/wiki/Fast_inverse_square_root

2024-10-01 01:28:49 UTC

- reply

This all seems unnecessarily indirect. If they want to reduce their quality standards so that they let more badly-written AI-generated slop through in place of actual research papers, in order to generate training data, why not just cut out the middlemen and use an AI to generate badly-written slop to use as training data?
Or maybe they think that they can escape the inevitable lawsuit for violating the terms of their data-supply contract by pointing to the authors and saying they are shocked, shocked to discover that the kind of author who would go for a cut-to-nothing review process would also use AI to help write their submissions?