Transcript Hunting for Sharp Thresholds

Hunting for Sharp
Thresholds
Ehud Friedgut
Hebrew University
Local properties
A graph property will be called
local if it is the property of
containing a subgraph from a
given finite list of finite graphs.
(e.g. “Containing a triangle or a
cycle of length 17”.)
AlmostNon-Theorem: If a monotone
graph property has a coarse
threshold then it is local.
approximable
by a local property.
Applications
• Connectivity
• Perfect matchings in graphs
hypergraphs
• 3-SAT
Assume, by way of
contradiction, coarseness.
Generalization to signed
hypergraphs
Use Bourgain’s Theorem.
Or, as verified by Hatami and Molloy:
Replace G(n,p) by F(n,p), a random 3-sat
formula, M by a formula of fixed size
etc.; (The proof of the original criterion
for coarseness goes through.)
Initial parameters
• It’s easy to see that
1/100n < p < 100/n
• M itself must be satisfiable
• Assume, for concreteness, that M
involves 5 variables x1,x2,x3,x4,x5 and
that setting them all to equal “true”
satisfies M.
Restrictive sets of variables
We will say a quintuple of variables
{x1,x2,x3,x4,x5} is restrictive if setting
them all to “true” renders F
unsatisfiable.
Our assumptions imply that at least a
(1-α)-proportion of the quintuples are
restrictive.
Erdős-Stone-Simonovits
The hypergraph of restrictive quintuples
is super-saturated : there exists a
constant β such that if one chooses 5
triplets they form a complete 5-partite
system of restrictive quintuplets with
probability at least β.
Placing clauses of the form ( x1 V x2 V x3)
on all 5 triplets in such a system renders
F unsatisfiable!
Punchline
Adding 5 clauses to F make it
unsatisfiable with probability at least
β2{-15},
so adding εn3p clauses does this w.h.p.,
and not with probability less than 1-2α.
Contradiction!
Applications
• Connectivity
• Perfect matchings in hypergraphs
• 3-SAT
Rules of thumb:
•If it don’t look local - then it ain’t.
•Semi-sharp
sharp .
•No non-convergent oscillations.
A semi-random sample of open
problems:
•Choosability (list coloring number)
•Ramsey properties of
random sets of integers
•Vanishing homotopy group
of a random 2-dimensional
simplicial complex.
A more theoretical open problem:
•F: Symmetric properties with
a coarse threshold have high
correlation with local properties.
•Bourgain: General properties
with a coarse threshold have
positive correlation with
local properties.
What about the common generalization?
Probably true...