New math post on my blog: A puzzle about representing numbers as a sum of 3-smooth numbers https://blog.plover.com/math/pow23tab.html

A Space of Their Own, a New Online Database, Will Feature Works by 600+ Overlooked Female Artists from the 15th-19th Centuries

http://www.openculture.com/2018/11/prepare-online-database-600-overlooked-female-artists-15th-19th-centuries.html

"Many of their female creators were acclaimed during their lifetimes. By the time Fortune [the founder of the project] set about restoring their work – and visibility – to the public view, they were virtually unknown, even to museum staff."

Via WikiProject Women in Red.

New Tools for Self-Construction: http://b3s23life.blogspot.com/2018/11/new-tools-for-self-construction.html

Self-constructing spaceships in Conway's Game of Life are getting smaller, more visually clear (not just looking like a line) and more varied. And there's a hint of a "metacell" that can simulate Life or other cellular automata, with empty space as its off state, so you could start any simulation with finitely many live cells. The key to all this is new software to find glider salvos that build constellations of still lifes.

New post: Gurobi versus the no-three-in-line problem

https://11011110.github.io/blog/2018/11/12/gurobi-vs-no.html

How well can a good but generic integer linear program solver stand up against 20-year-old problem-specific search code?

Where did all the circles in https://apod.nasa.gov/apod/ap181109.html come from? Some of them really are circles, traced by stars across the night sky. They form an elliptic pencil of circles (https://en.wikipedia.org/wiki/Apollonian_circles) converging to the north and south celestial poles. Others come from the latticework of a lookout tower, transformed into more pencils of circles. The horizon also appears, less clearly, as the small dark circle near the center of the image.

New blog post: Random no-three-in-line sets

https://11011110.github.io/blog/2018/11/10/random-no-three.html

Known constructions for many grid points with no three on a common line are based on algebraic curves and modular arithmetic. I look at how close one can get to them by using the probabilistic method instead.

@11011110 I have a different peeve: E. Demaine, M. Demaine, and Lubiw didn't actually prove the Fold and Cut theorem! Their straight-skeleton-based algorithm doesn't necessarily yield a finite number of folds, thanks to the possibility of "dense spiraling". (See Figure 17.10 in Geometric Folding Algorithms.) The first actual *proof* is your circle-packing argument with Bern, E. Demaine, and Hayes (1998), with some bugs corrected by E. Demaine and O'Rourke in (2006).

Two posts by Evelyn Lamb about the theorem that you can make any shape by folding+one cut, and a fold+cut alphabet by Erik and Marty Demaine and Katie Steckles: https://blogs.scientificamerican.com/roots-of-unity/the-queen-of-the-fold-and-cut-alphabet/ and https://blogs.scientificamerican.com/roots-of-unity/make-your-own-font-1-cut-at-a-time/

Small peeve: Lamb and Steckles omit credit for some theorem authors, particularly Lubiw.

If you want to design your own, the disk packing method is implemented at http://jorigami.sourceforge.net/ but I think the straight skeleton method produces prettier folding patterns.

The geometric quilts of Irena Swanson: https://www.reed.edu/reed_magazine/march2016/articles/features/irena-swanson.html

Swanson is a commutative algebraist, one of the new AMS Fellows. See also her own sites on quilting, http://people.reed.edu/~iswanson/quilt.html and https://www.tubepiecing.com/

The 2019 class of fellows of the American Mathematical Society is now out: https://www.ams.org/profession/ams-fellows/new-fellows

There are surprisingly many new fellows with a theoretical computer science connection, including Saugata Basu, Bonnie Berger, Aravind Srinivasan, Moshe Vardi, and Eric Vigoda.

Matteo García asks how to randomly sample degeneracy orderings of graphs (start with \(k=1\) and at each step remove a vertex of degree at most \(k\), or increase \(k\) when no such vertex remains): https://cstheory.stackexchange.com/q/41846/95

I think this question deserves more attention. My intuition is that it's hard (for instance it might be \(\#\mathsf{P}\)-complete to count degeneracy orderings of trees) but I don't see how to prove it.

1 In 4 Statisticians Say They Were Asked To Commit Scientific Fraud:

https://www.acsh.org/news/2018/10/30/1-4-statisticians-say-they-were-asked-commit-scientific-fraud-13554 (via https://news.ycombinator.com/item?id=18364518)

One of the reasons I like working in a discipline based more on proof and less on experiment: I have a difficult time imagining what "mathematical fraud" might be, or why one might be pressured to commit it. Uninteresting math, or more-complicated-than-necessary math, sure, but deliberately-wrong math? Why would you do that?

Symmetric graphs constructed as the state spaces of rolling dice of different shapes: https://math.stackexchange.com/questions/2972454/rolling-icosahedron-hamiltonian-path

It doesn't say so in the post, but Ed Pegg pointed out separately to me that if you do this with a regular octahedron (d8) you get the Nauru graph. A dodecahedron (d12) should get you a nice 5-regular 120-vertex graph (because each face has 10 orientations) – anyone have any idea what's known about this graph?

https://mathlesstraveled.com/2018/10/29/post-without-words-23/

A sequence of mathematical images in search of an explanation. What are these paths of randomly-placed dots that seem to explode in some sort of binary tree pattern from the bottom left corner of the images? (don't read the comments farther down on the post unless you want spoilers)

Meditative Geometric Shapes Doodled on Old Ledgers by Albert Chamillard: https://www.thisiscolossal.com/2018/11/geometric-drawings-by-albert-chamillard/

New post, 95 women of STEM: https://11011110.github.io/blog/2018/11/01/95-women-stem.html

(Or, how I've been spending my spare time in October creating new Wikipedia articles.)

I made a page for updates and errata to my book: http://www.ics.uci.edu/~eppstein/forbidden/

I had been planning to do this eventually but what triggered me to do it now was the discovery of a paper by Czumaj, Sohler, and Ziegler (ESA 2000, https://doi.org/10.1007/3-540-45253-2_15) on geometric property testing that I should have already been citing and that solved a problem I had listed as open on the sample complexity of testing for being in convex position. See the new page for details.

Yet another instance of graph theory before Euler's invention of the subject in 1736: https://plus.google.com/+JeffErickson/posts/TbsWRKnsC7R

(A few labeled graphs (with notes as vertices and intervals as edges), from the 1492 printing of Boethius's _De institutione musica_, posted by @jeffgerickson on Google+)

Wikipedia's Strickland affair: https://en.wikipedia.org/wiki/Wikipedia:Wikipedia_Signpost/2018-10-28/Op-ed

Strickland is a new Nobel prize winner who, before the prize, had never been put up for promotion to full professor (embarrassing her employer) and had two attempts at creating a Wikipedia article shot down (which should have, but apparently didn't, embarrassed the people who did it). This trio of op-eds examines how everyone responded, how we can do better, or (in the third case) why the writer thinks we shouldn't try to do better.

- Home page
- https://www.ics.uci.edu/~eppstein/

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

Joined Apr 2017