-
Which infinite graphs can DFS explore?
I recently revisited the Wikipedia article on normal spanning trees, rooted spanning trees of infinite undirected graphs that act like depth-first search trees in the sense that every non-tree edge of the graph connects an ancestor to a descendant. They exist in every connected countable undirected graph, but cannot always be generated by a depth-first search. It occurred to me to wonder: in which connected countable undirected graphs is it possible for a depth-first search to visit all vertices? It turns out to be possible if and only if the graph has one of the following two connectivity properties. Either:
-
Linkage
- Exchange rates between CS conferences (\(\mathbb{M}\)). Assuming that the people who publish in top conferences are equally productive, how many machine learning papers are the equivalent effort to one paper in other areas?
-
Congratulations, Dr. Zheng!
Today I served as the external member on the doctoral defense of Da Wei (David) Zheng, a student of Timothy Chan at the University of Illinois. He has an impressive portfolio of recent publications on geometric data structures and geometric graph algorithms, some of which featured in his thesis, From Geometry to Graphs and Back: Geometric Range Searching and Algorithms in Structured Graphs, and in his defense talk.
-
Linkage
-
The ancient Greek mathematics of distorted airplane propeller photos
When Hippias of Elis studied the curve that came to be known by his name, the quadratrix of Hippias, some 24 centuries ago, it is unlikely that he had in mind the distorted photographs of airplane propeller blades produced by a camera with a rolling shutter.
-
Linkage
- IEEE has a pseudoscience problem (\(\mathbb{M}\), via). “Unfortunately, bad science published by IEEE isn’t limited to boring applications of boring algorithms to boring data”: the post goes on to describe IEEE publications about computer-enhanced ayurveda, astrology, the supernatural potential of 5G cellphone signals in scientific traditional Chinese medicine, electro-homeopathy, and even two recent papers on perpetual motion.
-
Linkage
- Historic (but no longer extant) Native American settlements such as Buldam, California appear to have been removed from the online gazetteer of the USGS (\(\mathbb{M}\)). Other former settlements such as Rockport, California have not been erased. A discussion on Wikipedia suggests the difference may be that the native settlements did not have a precise known location.
-
Blooming caterpillars
When a polyhedron’s surface can be cut and flattened into a polygon, the resulting flattened shape is called a net, and the system of cuts is called an unfolding. A familiar example is the Latin cross of six squares, unfolded after cutting seven edges of a cube. This example is an edge unfolding: its cuts are on edges of the polyhedron, and the resulting net consists of faces of the polyhedron connected edge-to-edge. We don’t know whether all convex polyhedra have edge unfoldings (they do always have unfoldings of other types). We also don’t know whether every net has a blooming, a continuous motion from the cut surface of the polyhedron to its flat unfolded state, throughout which the moving surface avoids crossing itself and stays flat except at the uncut edges of the polyhedron. (Nets do always have continuous flattening motions if bending the faces is allowed; see my work on unfolding simply-connected developable surfaces). And when a net does have a blooming, we don’t know whether we can restrict the blooming to only increase dihedral angles monotonically.
-
Visualizing the Henson graph
When visualizing finite graphs, you can simply draw the whole graph. But that doesn’t really work for infinite graphs. What you need to visualize is not so much the graph itself, but the rule by which it is constructed.
-
Linkage with incoming gloom
- New book-sorting algorithm almost reaches perfection (\(\mathbb{M}\)): Quanta on the list labeling problem, based on “Nearly Optimal List Labeling” by Bender, Conway, Farach-Colton, Komlós, Koucký, Kuszmaul, and Saks, from FOCS 2024.
subscribe via RSS