New blog post: Layered pathwidth and its obstacles

I describe my new preprint with Dujmović, Joret, Morin, and Wood proving that a minor-closed graph family has bounded local pathwidth, linear local pathwidth, or bounded layered pathwidth iff it excludes an apex-tree, and compare analogous results in which the structure of a forbidden minor tells you about the structure of the graphs in a minor-closed family.

Theil–Sen (median slope) estimator, now a Good Article on Wikipedia:

This is a method for fitting a line to a set of data points by finding the median slope of lines through pairs of points. It is robust, meaning that (unlike ordinary least squares) a constant fraction of the data can be arbitrarily corrupted without affecting the goodness of fit.

New blog post: Laminar 3-separators,

In it, I describe my new SODA paper with Bruce Reed, “Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time”,, and how it's possible for an algorithm that works only on planar graphs to be useful as a subroutine for a different algorithm on nonplanar graphs (hint: they're not the same graphs).

Kokichi Sugihara wins the Best Illusion of the Year (again) with an orthogonal polyhedron! Or maybe a different orthogonal polyhedron. Or maybe a third one. Or maybe it's not actually orthogonal at all... (via

0xDE boosted

Inspired by a line in a textbook about imagining people standing in circles to show set membership, I've made a @glitch simulation of people spontaneously forming a Venn diagram:

An upper bound for Lebesgue’s universal covering problem

Philip Gibbs makes progress on the smallest area needed to cover a congruent copy of every diameter-one curve in the plane, with additional contributions from John Baez, Karine Bagdasaryan, and Greg Egan. See Baez's blog post for more. But why vixra??

Balogh and Solymosi's new paper
constructs \(n\) points in the plane, no four in line, with max general-position subset size \(O(n^{5/6+\epsilon})\), much better than the previous \(o(n)\). I recently rescued a Wikipedia article on Solymosi,, adding book references for his results, but omitted my favorite (this one) because it wasn't published. Now it is, but the book reference would be too self-serving to add...

Graduate student Urmila Mahadev devises interactive protocols that let you test whether a supposedly-quantum computer is really doing quantum stuff:

0xDE boosted

There! This is a 'proper' Delaunay Triangulation and Voronoi Diagram. I did mess up in a few places with the lines for the Voronoi part though, I was still freehanding it and not using pencil guidelines XD

#MastoArt #Math

Amazon trained a sexism-fighting, resume-screening AI with sexist hiring data, so the bot became sexist:

A Problem Fit for a Princess:

A post on the history of the Apollonian Gasket, a fractal formed by tangent circles, inspired by its use as the logo of the San Joaquin Math Teachers’ Circle.

A New ACO Center (guest post by Vijay Vazirani): blog.computationalcomplexity.o

A new blog post by Vijay Vazirani on the new "algorithms, combinatorics, and optimization" center he's been organizing at UC Irvine, connecting researchers in CS, mathematics, and the business school, and modeled after the success of similar programs at CMU and Georgia Tech.

The list of accepted papers at SODA (the annual ACM–SIAM conference on discrete algorithms, to be held next January in San Diego) is now out at

Via @JukkaSuomela's retweet of

0xDE boosted

I have been playing at generating snowflakes using cellular automata.

Looks like I may soon become more active here. Impetus: the impending shutdown of Google+. I may at least start mirroring what I post there to here and see how well that goes. For more discussion on alternative social media platforms see my G+ post,

0xDE boosted
0xDE boosted
0xDE boosted

Teruhisa Sugimoto has a draft paper that enumerates 17 types of convex, finitely surroundable pentagons! I hope to be able to read an English translation at some point. tilingpackingcovering.web.fc2.

0xDE boosted
Show more

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.