A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma

Simple item page
dc.creatorTao, Terence
dc.date2006-02-02
dc.date2007-06-04
dc.date.accessioned2026-07-07T08:07:29Z
dc.date.available2026-07-07T08:07:29Z
dc.descriptionWe introduce a correspondence principle (analogous to the Furstenberg correspondence principle) that allows one to extract an infinite random graph or hypergraph from a sequence of increasingly large deterministic graphs or hypergraphs. As an application we present a new (infinitary) proof of the hypergraph removal lemma of Nagle-Schacht-Rödl-Skokan and Gowers, which does not require the hypergraph regularity lemma and requires significantly less computation. This in turn gives new proofs of several corollaries of the hypergraph removal lemma, such as Szemerédi's theorem on arithmetic progressions.
dc.description39 pages, to appear, J. d'Analyse Mathematique. Proof of the relative independence property simplified; many suggestions of the referees implemented
dc.identifierhttps://arxiv.org/abs/math/0602037
dc.identifierhttp://arxiv.org/abs/math/0602037
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/130953
dc.subjectCombinatorics
dc.subjectDynamical Systems
dc.subjectProbability
dc.subject05C75; 60A10; 60C05; 28D15
dc.titleA correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma
dc.typetext

Files

Collections

arXiv