Category Archives: combinatorics

Random Graphs in NetworkX: My Spatial-Temporal Preferred Attachment Diversion

To take my mind off my meetings, I spent a little time modifying the Spatial Preferred Attachment model from Aiello, Bonato, Cooper, Janssen, and Prałat’s paper A Spatial Web Graph Model with Local Influence Regions so that it changes over time. Continue reading


Filed under combinatorics, probability

Gowers’s Polymath Experiment: Problem probably solved

A couple of weeks ago, I mentioned the exciting experiment in online math collaboration, where Tim Gowers invited the world to set out and develop a combinatorial proof of the density Hales-Jewitt theorem (DHJ). Big congratulations to them, because the problem is solved, probably. Summarizing why he spent his time on this particular problem, Terry Tao wrote:

I guess DHJ is known to experts in the field to be an interesting question, partly because it implies a number of other deep theorems (e.g. Szemeredi’s theorem, which was for instance a key tool in my result with Ben that the primes contain arbitrarily long arithmetic progressions), but also because it (until very recently) was one of the most prominent density Ramsey theorems that could only be proven by ergodic theoretic techniques. I myself am a big believer in exploiting more systematically the connections between ergodic theory, combinatorics, and Fourier analysis, and so this project was certainly very appealing to me. Besides, historically every new proof of Szemeredi’s theorem has led to a substantial amount of progress and activity in at least one subfield of mathematics; now that we have yet another proof (the fifth genuinely new proof of Szemeredi, by my count), one can hope that the tools developed here will have some applicability elsewhere.

Now, are there any applications of DHJ or Ramsey theory to Health Metrics? I wouldn’t say they are leaping out at me, but I wouldn’t rule it out either. When noisy data has unavoidable structure, some of the noise could be removed.


Filed under combinatorics