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?

Continue reading

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

Continue reading

Maximum weighted independent set – connected component

coloringpeteresen2Given 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.

clebschgraphk16_800 Continue reading

Generalized heaps

screen-shot-2016-10-27-at-10-31-39-amMin-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.

Continue reading

Obituaries: Herbert Scarf (1930 – 2015)

Herbert ScarfIn 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

Continue reading

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.

Continue reading

Obituaries: Alexander Grothendieck (1928–2014)

More will be told of this story as his voluminous writings from the hinterland are being read. But between 1945 and 1970 he published mathematics of unparalleled sweep and power, conveying escalations of abstraction to the solution of concrete problems, and this is the part we wish to appreciate.

Alexander Grothendieck 1928–2014 | Gödel’s Lost Letter and P=NP.