I’ve just uploaded to the arXiv my lecture notes “Structure and randomness in combinatorics” for my tutorial at the upcoming FOCS 2007 conference in October. This tutorial covers similar ground as my ICM paper (or slides), or my first two Simons lectures, but focuses more on the “nuts-and-bolts” of how structure theorems actually work to separate objects into structured pieces and pseudorandom pieces, for various definitions of “structured” and “pseudorandom”. Given that the target audience consists of computer scientists, I have focused exclusively here on the combinatorial aspects of this dichotomy (applied for instance to functions on the Hamming cube) rather than, say, the ergodic theory aspects (which are covered in Bryna Kra‘s lecture notes from Montreal, or my notes from Montreal for that matter). While most of the known applications of these decompositions are number-theoretic (e.g. my theorem with Ben Green), the number theory aspects are not covered in detail in these notes. (For that, you can read Bernard Host’s Bourbaki article, Ben Green‘s Gauss-Dirichlet article or ICM article, or my Coates article.)

### Recent Comments

### Articles by others

- Gene Weingarten – Pearls before breakfast
- Isaac Asimov – The relativity of wrong
- Jonah Lehrer – Don't! – the secret of self-control
- Julianne Dalcanton – The cult of genius
- Nassim Taleb – The fourth quadrant: a map of the limits of statistics
- Paul Graham – What You'll Wish You'd Known
- Po Bronson – How not to talk to your kids
- Scott Aaronson – Ten signs a claimed mathematical proof is wrong
- Timothy Gowers – Elsevier — my part in its downfall
- Timothy Gowers – The two cultures of mathematics
- William Thurston – On proof and progress in mathematics

### Diversions

- Abstruse Goose
- Assembler
- BoxCar2D
- Factcheck.org
- FiveThirtyEight
- Gapminder
- Literally Unbelievable
- Planarity
- PolitiFact
- Quite Interesting
- snopes
- Strange maps
- Television tropes and idioms
- The Daily Show with Jon Stewart
- The Economist
- The Onion
- The Straight Dope
- This American Life on the financial crisis I
- This American Life on the financial crisis II
- What if? (xkcd)
- White whine
- xkcd

### Mathematics

- 0xDE
- A Mind for Madness
- A Portion of the Book
- Absolutely useless
- Alex Sisto
- AMS blogs
- AMS Graduate Student Blog
- Analysis & PDE
- Analysis & PDE Conferences
- Annoying Precision
- Area 777
- Ars Mathematica
- ATLAS of Finite Group Representations
- Automorphic forum
- Avzel's journal
- Blog on Math Blogs
- Blog On Mathematical Journals
- blogderbeweise
- Bubbles Bad; Ripples Good
- Cédric Villani
- Climbing Mount Bourbaki
- Coloquio Oleis
- Combinatorics and more
- Compressed sensing resources
- Computational Complexity
- Concrete nonsense
- David Mumford's blog
- Delta epsilons
- DispersiveWiki
- Disquisitiones Mathematicae
- Embûches tissues
- Emmanuel Kowalski’s blog
- Encyclopedia of Mathematics
- Equatorial Mathematics
- fff
- Floer Homology
- Frank Morgan’s blog
- Gérard Besson's Blog
- Gödel’s Lost Letter and P=NP
- Geometric Group Theory
- Geometry and the imagination
- Geometry Bulletin Board
- Girl's Angle
- God Plays Dice
- Good Math, Bad Math
- Graduated Understanding
- Hydrobates
- I Woke Up In A Strange Place
- Igor Pak's blog
- Images des mathématiques
- In theory
- James Colliander's Blog
- Jérôme Buzzi’s Mathematical Ramblings
- Joel David Hamkins
- Journal of the American Mathematical Society
- Kill Math
- Le Petit Chercheur Illustré
- Lemma Meringue
- Lewko's blog
- Libres pensées d’un mathématicien ordinaire
- LMFDB – L-functions and modular forms database
- LMS blogs page
- London number theory
- Low Dimensional Topology
- M-Phi
- MAA MinuteMath
- Math Overflow
- Mathbabe
- Mathblogging
- Mathematical musings
- Mathematics Illuminated
- Mathematics in Australia
- Mathematics Jobs Wiki
- Mathematics Stack Exchange
- Mathematics under the Microscope
- Mathematics without apologies
- Mathlog
- MathOnline
- Mathtube
- Matt Baker's Math Blog
- Mixedmath
- Motivic stuff
- Much ado about nothing
- Multiple Choice Quiz Wiki
- neverendingbooks
- nLab
- Noncommutative geometry blog
- Nonlocal equations wiki
- Not "Not Even Wrong"
- Nuit-blanche
- Number theory web
- outofprintmath
- PDE blog
- Pengfei Zhang's blog
- Peter Cameron's Blog
- Phillipe LeFloch's blog
- ProofWiki
- Quomodocumque
- Random Math
- Reasonable Deviations
- Regularize
- Rigorous Trivialities
- Roots of unity
- Secret Blogging Seminar
- Selected Papers Network
- Sergei Denisov's blog
- Short, Fat Matrices
- Shtetl-Optimized
- Shuanglin's Blog
- Since it is not…
- Sketches of topology
- Soft questions
- Stacks Project Blog
- SymOmega
- tcs math
- TeX, LaTeX, and friends
- The accidental mathematician
- The capacity to be alone
- The Cost of Knowledge
- The Everything Seminar
- The Geomblog
- The Mathematics Literature Project
- The n-Category Café
- The n-geometry cafe
- The On-Line Blog of Integer Sequences
- The polylogblog
- The polymath blog
- The polymath wiki
- The Tricki
- The twofold gaze
- The Unapologetic Mathematician
- The value of the variable
- The World Digital Mathematical Library
- Theoretical Computer Science – StackExchange
- Tim Gowers’ blog
- Tim Gowers’ mathematical discussions
- Todd and Vishal’s blog
- Van Vu's blog
- Vaughn Climenhaga
- Vieux Girondin
- Visual Insight
- Vivatsgasse 7
- Williams College Math/Stat Blog
- Windows on Theory
- Wiskundemeisjes
- XOR’s hammer
- Zhenghe's Blog

### Selected articles

- A cheap version of nonstandard analysis
- A review of probability theory
- American Academy of Arts and Sciences speech
- Amplification, arbitrage, and the tensor power trick
- An airport-inspired puzzle
- Benford's law, Zipf's law, and the Pareto distribution
- Compressed sensing and single-pixel cameras
- Einstein’s derivation of E=mc^2
- On multiple choice questions in mathematics
- Quantum mechanics and Tomb Raider
- Real analysis problem solving strategies
- Sailing into the wind, or faster than the wind
- Simons lectures on structure and randomness
- Small samples, and the margin of error
- Soft analysis, hard analysis, and the finite convergence principle
- The blue-eyed islanders puzzle
- The cosmic distance ladder
- The federal budget, rescaled
- Ultrafilters, non-standard analysis, and epsilon management
- What is a gauge?
- What is good mathematics?
- Why global regularity for Navier-Stokes is hard

### Software

### The sciences

### Top Posts

- A cheap version of Halasz's inequality
- 275A, Notes 5: Variants of the central limit theorem
- Career advice
- Real stable polynomials and the Kadison-Singer problem
- Books
- 275A, Notes 0: Foundations of probability theory
- Klaus Roth
- Does one have to be a genius to do maths?
- On writing
- The Euler-Maclaurin formula, Bernoulli numbers, the zeta function, and real-variable analytic continuation

### Archives

- November 2015 (6)
- October 2015 (5)
- September 2015 (5)
- August 2015 (4)
- July 2015 (7)
- June 2015 (1)
- May 2015 (5)
- April 2015 (4)
- March 2015 (3)
- February 2015 (4)
- January 2015 (4)
- December 2014 (6)
- November 2014 (5)
- October 2014 (4)
- September 2014 (3)
- August 2014 (4)
- July 2014 (5)
- June 2014 (5)
- May 2014 (5)
- April 2014 (2)
- March 2014 (4)
- February 2014 (5)
- January 2014 (4)
- December 2013 (4)
- November 2013 (5)
- October 2013 (4)
- September 2013 (5)
- August 2013 (1)
- July 2013 (7)
- June 2013 (12)
- May 2013 (4)
- April 2013 (2)
- March 2013 (2)
- February 2013 (6)
- January 2013 (1)
- December 2012 (4)
- November 2012 (7)
- October 2012 (6)
- September 2012 (4)
- August 2012 (3)
- July 2012 (4)
- June 2012 (3)
- May 2012 (3)
- April 2012 (4)
- March 2012 (5)
- February 2012 (5)
- January 2012 (4)
- December 2011 (8)
- November 2011 (8)
- October 2011 (7)
- September 2011 (6)
- August 2011 (8)
- July 2011 (9)
- June 2011 (8)
- May 2011 (11)
- April 2011 (3)
- March 2011 (10)
- February 2011 (3)
- January 2011 (5)
- December 2010 (5)
- November 2010 (6)
- October 2010 (9)
- September 2010 (9)
- August 2010 (3)
- July 2010 (4)
- June 2010 (8)
- May 2010 (8)
- April 2010 (8)
- March 2010 (8)
- February 2010 (10)
- January 2010 (12)
- December 2009 (11)
- November 2009 (8)
- October 2009 (15)
- September 2009 (6)
- August 2009 (13)
- July 2009 (10)
- June 2009 (11)
- May 2009 (9)
- April 2009 (11)
- March 2009 (14)
- February 2009 (13)
- January 2009 (18)
- December 2008 (8)
- November 2008 (9)
- October 2008 (10)
- September 2008 (5)
- August 2008 (6)
- July 2008 (7)
- June 2008 (8)
- May 2008 (11)
- April 2008 (12)
- March 2008 (12)
- February 2008 (13)
- January 2008 (17)
- December 2007 (10)
- November 2007 (9)
- October 2007 (9)
- September 2007 (7)
- August 2007 (9)
- July 2007 (9)
- June 2007 (6)
- May 2007 (10)
- April 2007 (11)
- March 2007 (9)
- February 2007 (4)

### Categories

- expository (233)
- tricks (8)

- guest blog (9)
- Mathematics (642)
- math.AC (5)
- math.AG (37)
- math.AP (84)
- math.AT (15)
- math.CA (127)
- math.CO (151)
- math.CT (6)
- math.CV (13)
- math.DG (32)
- math.DS (68)
- math.FA (22)
- math.GM (9)
- math.GN (21)
- math.GR (78)
- math.GT (12)
- math.HO (9)
- math.IT (9)
- math.LO (46)
- math.MG (34)
- math.MP (25)
- math.NA (13)
- math.NT (128)
- math.OA (17)
- math.PR (86)
- math.QA (5)
- math.RA (24)
- math.RT (21)
- math.SG (4)
- math.SP (45)
- math.ST (5)

- non-technical (122)
- admin (42)
- advertising (18)
- diversions (4)
- media (11)
- journals (2)

- obituary (9)

- opinion (27)
- paper (161)
- question (98)
- polymath (69)

- talk (63)
- DLS (19)

- teaching (148)
- 245A – Real analysis (11)
- 245B – Real analysis (19)
- 245C – Real analysis (6)
- 254A – analytic prime number theory (16)
- 254A – ergodic theory (18)
- 254A – Hilbert's fifth problem (12)
- 254A – random matrices (14)
- 254B – expansion in groups (8)
- 254B – Higher order Fourier analysis (9)
- 275A – probability theory (6)
- 285G – poincare conjecture (20)
- Logic reading seminar (8)

- travel (25)
- Uncategorized (2)

### Google+ feed

- An error has occurred; the feed is probably down. Try again later.

additive combinatorics
almost orthogonality
approximate groups
arithmetic progressions
Ben Green
Cauchy-Schwarz
Cayley graphs
central limit theorem
circular law
compactness
compressed sensing
concentration compactness
correspondence principle
eigenvalues
Elias Stein
Emmanuel Breuillard
entropy
equidistribution
ergodic theory
expander graphs
exponential sums
finite fields
Fourier transform
Four Moment Theorem
Freiman's theorem
Gowers uniformity norms
gradient shrinking solitons
graph theory
Gromov's theorem
GUE
Hilbert's fifth problem
hypergraphs
inverse conjecture
Kakeya conjecture
Lie algebras
Lie groups
Littlewood-Offord problem
Mobius function
moment method
multiple recurrence
Navier-Stokes equations
nilpotent groups
nilsequences
NLS
nonstandard analysis
parity problem
politics
polymath1
polymath8
polynomial method
polynomials
prime numbers
prime number theorem
project heatwave
random matrices
randomness
random walks
Ratner's theorem
regularity lemma
Ricci flow
Riemann zeta function
Schrodinger equation
Selberg sieve
sieve theory
spectral theorem
structure
Szemeredi's theorem
Tamar Ziegler
ultrafilters
ultraproducts
universality
Van Vu
wave maps
Weil conjectures
Yitang Zhang

### The Polymath Blog

- Polymath10 is now open 6 November, 2015
- The Erdős discrepancy problem has been solved by Terence Tao 22 September, 2015
- Two polymath (of a sort) proposed projects 20 January, 2014
- Polymath9: P=NP? (The Discretized Borel Determinacy Approach) 4 November, 2013
- Polymath8 – A Success ! 20 September, 2013
- Polymath7 research thread 5: the hot spots conjecture 9 August, 2013
- Polymath proposal: bounded gaps between primes 4 June, 2013
- Polymath proposal (Tim Gowers): Randomized Parallel Sorting Algorithm 2 March, 2013
- Next Polymath Project(s): What, When, Where? 14 February, 2013
- Polymath7 research threads 4: the Hot Spots Conjecture 10 September, 2012

### Mathematics in Australia

- Save pure mathematics at the VU University of Amsterdam 30 April, 2011
- ERA results for mathematical sciences in Australia 15 February, 2011
- Junior positions at ANU 8 November, 2010
- AustMS now on twitter 10 October, 2010
- Research not bad, but not stellar 9 May, 2010
- L’Oréal Australia For Women In Science Fellowships 11 April, 2010
- Postdoctoral position (Level A) in mathematics at Australian National University 18 January, 2010
- Cheryl Praeger named as 2009 Western Australian Scientist of the Year 2 December, 2009
- Positions at Australian National University 4 November, 2009
- Mathematics skills out for the count 26 October, 2009

## 21 comments

Comments feed for this article

1 August, 2007 at 4:03 pm

Top Posts « WordPress.com[…] Structure and randomness in combinatorics I’ve just uploaded to the arXiv my lecture notes “Structure and randomness in combinatorics” for my […] […]

2 August, 2007 at 9:32 am

AnonymousHOWDY DR. T!

The linked article references “On the structure of certain infinite random hypergraphs” by one T. Austin.

If you know of a version of the cited preprint on the internet, could you be so kind as to link to it? I have had little luck with google and arxiv searches.

Sincerely,

Nate

2 August, 2007 at 6:31 pm

AnonymousProf Tao,

I am wondering if the following is known. does Green’s arithmetic regularity lemma over the Hamming cube extend to higher uniformity norms? More specifically, for every k>2 and eps, every function f, is there also a subspace V of constant codimension, such that f on most translates of V have small Gowers k-uniformity norm?

If this is known (or for specific k), can you provide a reference? Thanks.

Sincerely,

Victor

3 August, 2007 at 9:44 am

Terence TaoDear Nate,

Tim Austin’s article is in draft form right now and should be available in a few weeks (it is pending the finalisation of another joint article between Tim and myself which uses Tim’s structure theorem for a property testing application – stay tuned!).

Dear Victor,

There is a higher version of this lemma known, at least in the k=3 case; the one new twist is that rather than slicing up the Hamming cube into translates of a vector space (or in other words, level sets of a few linear functions), one needs to slice up the Hamming cube instead into

quadraticvarieties – level sets of a few quadratic functions. One can see the need for this by looking at the standard maximum-rank quadratic form ; no amount of slicing into linear subspaces will eradicate the quadratic nature of this form, and so you cannot get k=3 Gowers uniformity of the function (minus its average, of course) unless you use quadratic slices (or if you use alotof linear slices, at least n of them).A reference for this is Proposition 3.9 of Ben Green’s Montreal lecture notes:

http://www.arxiv.org/abs/math.CA/0604089

If the Gowers inverse conjecture is true for higher k, then there will be analogues for higher k also (where now we slice using polynomials of degree k-1).

3 August, 2007 at 1:14 pm

AnonymousHi Terry, thanks for the beautifully written article. A small correction: Reed-Solomon should be replaced by Reed-Muller.

3 August, 2007 at 3:58 pm

Terence TaoThanks for the correction!

5 August, 2007 at 5:10 pm

DougWhat happens if one writes the combinatorial formulas for nCr, nPr in terms of the gamma function? Does this lead to randomness in combinatorics? Does it permit a combinatorics of objects arbitrary picked from two places along a continous interval among the reals? Would we need a different notion of “choosing” and “permutation”, or would it permit a combinatorics of fractional-valued objects with similar notions to one already? Supposing we can’t exactly count how many objects we have, but say we have approximately 6 objects and then we choose approximately 4 objects, would such a combinatorics allow us to compute how many “possibilities” would exist?

I can’t say that writing the combinatorial formulas in terms of the gamma function makes sense for me, at least not at this time. But, formally it seems permissible… at least if we take the combinations and permutations formulas as axioms, even if my little mind doesn’t get how to understand it (possibly yet). I’d guess someone could make some sense of this idea someday, but if you think really not, by all means have a laugh at this idea.

7 August, 2007 at 7:18 pm

ZaiakuIntersting write. Got me thinking tonight on this one.

20 August, 2007 at 2:32 pm

NATEHowdy.

Did you (or somebody else) ever write up a version of your variant on the hypergraph counting lemma to cover the case of non-partite hypergraphs?

20 August, 2007 at 3:02 pm

Terence TaoDear NATE,

Not as far as I know. You can “fake” it by interpreting a non-partite k-uniform hypergraph on n vertices as a k-partite k-uniform hypergraph on nk vertices in the obvious manner, and applying the regularity lemma to that, but it’s not fully satisfactory because the lower order hypergraphs that come out of that regularity lemma are not symmetric enough to have arisen from a non-partite hypergraph on the original vertex set, unless you do some technical trickery to force the symmetry. But probably the most direct way to proceed is to repeat the proof in the non-partite setting, working in spaces of functions which are symmetric with respect to the permutation group on k elements, and making sure that all the partitions etc. which arise are also symmetric (or at least equivariant) with respect to such permutations.

Of course, one probably needs to have some non-trivial application in mind for the regularity lemma in order to go to all this trouble; one already has the hypergraph regularity lemmas of Gowers and of Rodl-Nagle-Schacht-Skokan which are more or less of comparable strength.

20 August, 2007 at 5:11 pm

NATEI have a definite application in mind, and I am shopping around for which version of hypergraph regularity will most easily lend itself to the generalization that I have in mind.

If you have any insights on which formulations are better in different contexts, I’d love to hear them.

20 August, 2007 at 5:53 pm

Terence TaoWell, for obvious reasons I am not the most objective judge of the relative worth of my version of the hypergraph regularity lemmas of Gowers and Rodl et al :-) . The latter has been used since in several places by Rodl and his school, so is presumably a good general-purpose tool. Gowers’ version seems to extend relatively well to sparse settings – Ben Green and I (very implicitly) took advantage of this in our papers on the primes. My version has an additional parameter F() which turns out to be useful in some property testing applications, but one can replicate this effect using other versions of the regularity lemma. But they are all fairly close to each other. There are also some newer variants; Ishigami has a version based on random sampling, and then there are the infinitary variants of Elek-Szegedy and also of myself (and a forthcoming paper of Austin). There are also ways to use graph and hypergraph limits to avoid the need to explicitly invoke the regularity lemma, as pursued by Lovasz-Szegedy and Borg-Chayes-Lovasz-Sos. For a more direct approach to understanding hypergraph densities there is also the abstract approach of Razborov, again avoiding an explicit use of the regularity lemma.

So we have sort of an embarrassment of riches here; hopefully there will be some unification and clarity in the near future when the relationships between all these approaches become better understood.

20 August, 2007 at 6:24 pm

NATEhow can the parameterization of the growth function help with property testing?

20 August, 2007 at 7:08 pm

Terence TaoDear Nate,

This can come in handy when dealing with a graph or hypergraph property which is equivalent to not having any copies of any forbidden subgraph or subhypergraph in an infinite family. For instance, the property of a graph being bipartite is equivalent to having all odd cycles forbidden. (Let’s stick here to graphs for simplicity.)

The problem here is that the graphs in the forbidden family can be arbitrarily large; for instance one needs to exclude odd cycles of arbitrarily high length in order to be sure one is bipartite. But if the graph is of a simple form, one can do better. For instance, if a graph has only n vertices, then one only needs to forbid odd cycles of length at most n before one can be confident that one is bipartite. A little more interestingly, if a graph can be partitioned into n cells, such that the graph is either complete or empty between any pair of cells, one again only needs to consider odd cycles of length at most n.

This fact comes in handy in property testing when combined with the regularity lemma; one first regularises the graph by dividing the vertices into, say, n classes. From the above discussion, we see that for certain graphs associated to these classes, we can test certain properties using only subgraphs of size at most F(n) for some function F that depends on the property. Now, we would like the regularity given by the regularity lemma to be as high a quality as 1/F(n) in order that we can still count subgraphs of this size. With the usual regularity lemma this is unrealistic; we cannot make the regularity of the graph depend on the number of cells (instead, the relationship goes the other way). But with enhanced versions of the regularity lemma (not just mine, but also an earlier regularity lemma of Alon, Fischer, Krivelevich, and Szegedy) one can largely get around this obstacle by choosing the growth function suitably.

As far as I am aware, this trick was first introduced by Alon and Shapira to show that every monotone graph property is testable.

22 August, 2007 at 1:19 pm

NATEThanks for your replies, they were a big help. I am pretty sure that Ishigami’s version does most of what I want, so that saves me some time.

23 October, 2007 at 10:52 am

FOCS slides: structure and randomness in combinatorics « What’s new[…] these days in additive combinatorics and graph theory to distinguish structure and randomness. In a previous blog post, I had already mentioned that my lecture notes for this were available on the arXiv; now the slides […]

24 November, 2008 at 10:55 pm

Decomposition Results and Regularity Lemmas « in theory[…] Many examples of such results are given in the paper accompanying Terry Tao’s tutorial at FOCS’07. […]

27 April, 2009 at 8:16 am

FuchsTerence,

Is your work somewhat related to Ramsey theory?

Sincerely,

Fuchs

12 February, 2010 at 10:46 pm

An arithmetic regularity lemma, an associated counting lemma, and applications « What’s new[…] between structure and randomness”, as discussed for instance in my ICM article or FOCS article. In the degree case , this result is essentially due to Green. It is powered by the inverse […]

8 April, 2010 at 9:54 am

254B, Notes 2: Roth’s theorem « What’s new[…] viewed as the graph-theoretic analogue of this Fourier-analytic result; see this paper of mine (or my FOCS paper) for further discussion. The double iteration required to prove Theorem 10 means that the bounds […]

20 May, 2010 at 9:45 pm

254B, Notes 5: The inverse conjecture for the Gowers norm I. The finite field case « What’s new[…] a proof, see this paper of mine. The argument is similar to that appearing in Theorem 10 of Notes 2, but the discrete nature of […]