Structure and randomness in combinatorics

2007/07/29 by Tao, Terence · 4 citations
#05C75 #11B75 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0707.4269

Abstract

Combinatorics, like computer science, often has to deal with large objects of unspecified (or unusable) structure. One powerful way to deal with such an arbitrary object is to decompose it into more usable components. In particular, it has proven profitable to decompose such objects into a structured component, a pseudo-random component, and a small component (i.e. an error term); in many cases it is the structured component which then dominates. We illustrate this philosophy in a number of model cases.

Cited by

• Triangle Detection in H-Free Graphs
• Bounds for monochromatic solutions to \x+y,xy\
• A note on lower bounds for arithmetic regularity partitions
• Learning stabilizer structure of quantum states

Related

• Pseudorandomness and Combinatorial Constructions
• Random generation of combinatorial structures: Boltzmann samplers and beyond
• Permute, Graph, Map, Derange
• Probabilistic combinatorics at exponentially small scales
• A Model for Combinatorial Dictionary Learning and Inference