# independent set

## The Double Cap Conjecture ★★

Author(s): Kalai

**Conjecture**The largest measure of a Lebesgue measurable subset of the unit sphere of containing no pair of orthogonal vectors is attained by two open caps of geodesic radius around the north and south poles.

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

## Hitting every large maximal clique with a stable set ★★

**Conjecture**There is a universal constant such that every graph contains a stable set which intersects every maximal clique of size .

**Conjecture**Every graph contains a stable set which intersects every maximal clique of size .

Keywords: independent set; maximal clique

## Aharoni-Berger conjecture ★★★

**Conjecture**If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition