# Obituaries: Maryam Mirzakhani (1977 – 2017)

Maryam Mirzakhani died today. Terrance Tao writes about her. Elsewhere, Derrida – writing about Deleuze (I’ll Have to Wander All Alone): “Too much to say, and I don’t have the heart for it today.” It is because:

death takes from us not only some particular life within the world, some moment that belongs to us, but, each time, without limit, someone through whom the world, and first of all our own world, will have opened up in a both finite and infinite—mortally infinite—way.

Dynamic of the Moduli Spaces of Curves

# A fearful sphere, whose center is everywhere

In a beautiful article, The Mathematics of DoodlingRavi Vakil poses two problems:

1. Given a random curve, like a doodle, in what sense do closed curves successively drawn around the doodle become more and more circular?
2. How do geometric invariants, like area and volume, of the closed curves relate with the original shape and with each other?

# 2-butterfly derangement

The hallmark of the Cooley-Tukey algorithm for  Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

Three butterflies – FFT flow graph, shuffling network, and a nonblocking interconnect

# Maximum weighted independent set – connected component

Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight. Continue reading

# Maximum weighted independent set – singletons and forest

Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.

1. At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
2. Any two restaurants must be at least 2 miles apart.

# Generalized heaps

Min-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

# Obituaries: Herbert Scarf (1930 – 2015)

In addition to inventory policy, Scarf had at least four more major breakthroughs. Perhaps his most famous discovery is the Scarf algorithm.  Arrow and Debreu had proved that the equations describing economic equilibrium always have a solution when goods are divisible, but they were baffled by the problem of how to find one, except in special cases. The Scarf algorithm always finds an equilibrium, no matter how complicated the economy. This gave applied economists the ability to work with much more realistic models of the economy and thus to predict the consequences of major policy reforms including NAFTA and the U.S. tax system.

In memoriam: Herbert Scarf, pioneering economist and inspiring teacher

# Continued Fractions

Farey tessellation in complex plane

In fact, the matrix formulation of Fibonacci numbers mentioned before can be generalized to represent any 2-D matrix and, by way of continued fractions, any real number – not just the golden mean. This post is inspired from David Austin’s AMS feature column and draws on Phillipe Flajolet’s beautiful survey on continued fractions to set the stage for a future post on Diophantine approximation.