History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees

One of the most basic problems in dynamic graph algorithms is to maintain a maximal matching as edges are inserted and deleted over time. In a line of work started by Baswana, Gupta and Sen, and then completed by Solomon, it was shown how to solve this problem in amortized expected time $O(1)$ per update. (Interestingly, achieving worst-case expected $O(1)$ remains open.)