Tag · 4 problems · 3 fields

Open problems tagged extremal

4 problems in the Math Lab index touch extremal, spanning Graph Decompositions, Graph Theory, Combinatorics. Each carries a precise statement, an honest status, and a computational line of attack.

Erdős–Sós conjectureGraph Decompositionsuntouched

Every graph with average degree greater than k − 1 contains every tree with k edges as a subgraph.

Frankl's union-closed sets conjectureGraph Theoryuntouched

In every finite union-closed family of sets (other than {∅}), some element belongs to at least half of the sets.

No-three-in-line problemGraph Theoryuntouched

How many points can be placed in an n×n grid with no three collinear? At most 2n (two per row), and 2n is achieved for all n up to at least 46 — but conjecturally only ~1.814n is possible for large n.

Sunflower conjectureCombinatoricsuntouched

Erdős–Rado: any family of more than C(r)^w sets, each of size w, contains an r-sunflower (r sets with identical pairwise intersections). The conjecture puts C(r) independent of w.