11011110

Jun 15, 2019
Linkage for the end of an academic year

The Spring term just ended at UCI (we’re on a quarter system, so we run later into June and then start up again later in September than most other US universities). I haven’t yet turned in my grades, but I can already feel summer setting in.
Jun 11, 2019
Dancing arc-quadrilaterals

Several of my past papers concern Lombardi drawing, which I and my coauthors named after conspiracy-theory artist Mark Lombardi. In this style of drawing, edges are drawn as circular arcs, and must meet at equal angles around every vertex. Not every graph has such a drawing, but many symmetrical graphs do (example below: the smallest zero-symmetric graph with only two edge orbits).
Jun 7, 2019
A little knowledge can make the next step harder

Suppose you have a fill-in-the-unknowns puzzle, like Sudoku. Can making some deductions and filling in those parts of the puzzle make the whole thing harder to solve than it was before you started? Sometimes, yes!
May 31, 2019
Linkage
- No maths for Europe ( $\mathbb{M}$ ). Sadly, the EU parliament has passed up a chance to find a nice (or even not-so-nice) formula for its apportionment of seats to countries, instead opting for back-room deals and numbers pulled out of a hat.
May 27, 2019
Shattering and quasipolynomiality
An inadequately-explained phenomenon in computational complexity theory is that there are so few natural candidates for $\mathsf{NP}$ -intermediate problems, problems in $\mathsf{NP}$ but neither in $\mathsf{P}$ nor $\mathsf{NP}$ -complete. Of course, if $\mathsf{P}=\mathsf{NP}$ there are none, and the dichotomy theorem implies that there are no intermediate Boolean constraint satisfaction problems. But there are a lot of other types of problems in $\mathsf{NP}$ , and a theorem of Ladner¹ shows that there should be an infinite hierarchy of degrees of hardness within $\mathsf{NP}$ . So where are all the members of this hierarchy, and why are they so shy?
1. Ladner, Richard (1975), “On the structure of polynomial time reducibility”, J. ACM 22 (1): 155–171. ↩
May 25, 2019
More matching-mimicking networks

My paper with Vijay Vazirani on parallel matching (soon to appear in SPAA) is based on the idea of a “matching-mimicking network”. If $G$ is a graph with a designated set $T$ of terminal vertices, then a matching-mimicking network for $(G,T)$ is another graph $H$ with the same terminals that has the same pattern of matchings. Here, by a pattern of matchings, I mean a family of subsets of $T$ , the subsets that can be covered by a matching that also covers all non-terminal vertices. We included a messy case analysis that, after some simplifications due to symmetry, had 21 cases for the matching mimicking networks on at most three terminals.
May 21, 2019
Congratulations, Dr. Tillman!

Today I participated in the successful dissertation defense of Bálint Tillman, a student of Athina Markopoulou in the UCI Graduate Program in Networked Systems.
May 15, 2019
Linkage
- El poema de los números primos ( $\mathbb{M}$ ). Exhibit of the mathematically-inspired artworks of Esther Ferrer, at Tabakalera in San Sebastián, Spain.
May 2, 2019
Playing with model trains and calling it graph theory
You’ve probably played with model trains, for instance with something like the Brio set shown below.¹ And if you’ve built a layout with a model train set, you may well have wondered: is it possible for my train to use all the parts of my track?
1. Searching on tineye finds that this image was on Amazon in 2008. Presumably it was supplied to them by Brio? ↩
Apr 30, 2019
Linkage
- Good article, terrible headline ( $\mathbb{M}$ ). Bill Gasarch rants about several recent instances of clickbaity, inaccurate, and overhyped media coverage of theoretical computer science topics. I suspect the answer to his question “is it just our field?” is no.