Linkage
-
The Pentium as a Navajo weaving (\(\mathbb{M}\)), a 1994 rug by Marilou Schultz in the the National Gallery of Art designed from an image of the Intel Pentium integrated circuit.
-
On matching algorithms to solve single rows, columns, and boxes of sudoku puzzles (\(\mathbb{M}\)). As mentioned in my first blog post, 19 years ago.
-
Planar point sets with forbidden four-point patterns and few distinct distances (\(\mathbb{M}\)), Terry Tao. The forbidden patterns (as befits the problem) involve distances rather than order types. They are sets of four points with fewer than five distinct distances (classified into eight types) and the result is that some sets of \(n\) points avoiding these patterns nevertheless have only \(o(n^2)\) distances, solving an old Erdős problem. The solution combines random sampling of a grid (which reduces all but one of the patterns to few enough instances that you can afford to delete one more point per remaining one) with the modular parabola idea used e.g. by Erdős in the no-3-in-line problem (which without randomization kills the remaining pattern but not all the others).
-
Two new Wikipedia Good Articles (\(\mathbb{M}\)):
-
Skolem’s paradox, the seeming contradiction between the Löwenheim–Skolem theorem (first order theories such as ZFC have countable models) and Cantor’s theorem (there exists an uncountable set). In a countable model of ZFC, only countably many elements can model members of an uncountable set like \(\mathbb{R}\), but their countability is not visible within the model. This idea led to the “Skolemite” philosophy that all sets are secretly countable from some external view of set theory. I reviewed this for GA but the edits to bring it up to GA standard were by another editor, Pagliaccious.
-
Universal vertex, a vertex in a graph that is adjacent to all others. Although seemingly very basic, this touches on some nontrivial ideas: for instance, almost all cop-win graphs are cop-win because they have a universal vertex. And for an even number of labeled vertices, the number of graphs that include a universal vertex is odd, a property that is central to proving the evasiveness of having a universal vertex (if you learn about the graph by testing pairs of vertices for adjacency, you may be forced to test all pairs before finding out whether it has a universal vertex).
-
-
An annoyance in graph algorithms (\(\mathbb{M}\)): if your graph API gives you only one chance to list the neighbors of each vertex, then remembering them blows up the space for depth-first search from linear in the number of vertices to linear in the number of edges. You can work around this if all you need is the depth-first search tree but it’s still a problem for DFS-based algorithms that do something for each non-tree edge.
-
Katrine Hildebrandt embraces symmetry in paper, wire, and reed (\(\mathbb{M}\)), with geometric art often featuring concentric circles and parallel or radiating lines.
-
A new high-rank elliptic curve and a new book that systematically catalogues Diophantine equations (\(\mathbb{M}\)).
-
Lance Fortnow’s favorite theorem of the month: quasipolynomial time for parity games (\(\mathbb{M}\)).
-
Updated slides for my talk “Computational Complexities of Folding” (\(\mathbb{M}\)), which I gave again at JCDCG\(^3\) 2024. Compared to the OSME version, there’s some new material (and some removals of unimportant slides to make room):
-
It’s \(\mathsf{\#P}\)-complete to count flat-folded states for the same model of folding for which I already proved \(\mathsf{PSPACE}\)-completeness of reconfiguration.
-
It’s undecidable to determine whether a finite square of paper with a fractal infinite crease pattern can fold flat. This strengthens recent results of Hull and Zakharevich by using a finite rather than infinite sheet, by avoiding the use of optional folds, by using rational coordinates rather than multiples of \(\sqrt{3}\), and by simplifying the undecidable problem statement to flat-foldability instead of whether a certain finite perturbation to a repeating pattern remains finite.
-
-
Dan Gardner rebuts the idea that Wikipedia has become “Wokepedia” (\(\mathbb{M}\), via). In related Wikipedia news, Nicole Venus studies “the representation of female economists on Wikipedia” (via Ipigott on WikiProject Women in Red). Although Venus’s study showed the women in her data set to be 53% less likely than men to have a Wikipedia biography, much of that gap comes from differences in their visible accomplishments (likely caused by biases elsewhere, but beyond the control of Wikipedia editors). When that is factored out, Venus found that women were still 9% less likely to be profiled than men of comparable accomplishment. Initiatives to create more articles on women (like Women in Red) have helped lower that number, and Venus didn’t really see any systematic anti-women editing efforts on Wikipedia; she attributes the remaining gap to a greater tendency for self-promotion among men than women.
-
What makes mathematicians believe unproved mathematical statements? (\(\mathbb{M}\)), Timothy Gowers in Ann. Math. Phil. (2023).
-
Ordinary graphs (\(\mathbb{M}\)). Ed Pegg constructs some well-known graphs (the Shrikhande Graph, Petersen Graph, and Cuboctahedral Graph) from the ordinary lines of certain symmetric configurations of points. He finds two more interesting regular graphs that appear not to be so famous from the 16-point orchard configuration and the Grünbaum–Rigby configuration, and asks what other interesting graphs might be formed in the same way.
-
Cheating at scale (\(\mathbb{M}\)), on the difference in what you gain from poring over textbooks searching for a solved problem resembling your assigned problem, versus just asking an LLM to solve it for you. See also Ted Chiang in The New Yorker on why he thinks AI cannot make art: “Using ChatGPT to complete assignments is like bringing a forklift into the weight room; you will never improve your cognitive fitness that way.” (Via.)
-
A too-cute trick for zero-based indexing in Python from the end of an array backwards (\(\mathbb{M}\)):
A[~0],A[~1],A[~2], …