Examples ·k-CNF formula .(x1 V-x2 VX3)A (x2 Vx7V x8)A (x3 Vx4 Vx5) Each clause has exactly k literals Each variable appears in at most d clauses Satisfiableif ·Then p(Φ)=2-kand△（Φ）≤dk d s 2k ·Hypergraph coloring Each hyperedge has k vertices Each hyperedge intersects at most A other hyperedges Properly colorable if The color of each vertex chooses from q colors △sqk ·Then p(Φ)=ql-kand△（Φ）=△+1 Examples • 𝑘-CNF formula • 𝑥1 ∨ ¬𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥7 ∨ 𝑥8 ∧ ¬𝑥3 ∨ ¬𝑥4 ∨ 𝑥5 • Each clause has exactly 𝑘 literals • Each variable appears in at most 𝑑 clauses • Then 𝑝 Φ = 2 −𝑘 and Δ Φ ≤ 𝑑𝑘 • Hypergraph coloring • Each hyperedge has 𝑘 vertices • Each hyperedge intersects at most Δ other hyperedges • The color of each vertex chooses from 𝑞 colors • Then 𝑝 Φ = 𝑞 1−𝑘 and Δ Φ = Δ + 1 Satisfiable if 𝑑 ≲ 2 𝑘 Properly colorable if Δ ≲ 𝑞 𝑘