Home » Keyword index

independent set


Combinatorics

The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of $ \mathbb{R}^n $ containing no pair of orthogonal vectors is attained by two open caps of geodesic radius $ \pi/4 $ around the north and south poles.

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

Posted by Jon Noel
updated September 15th, 2015
add new comment
Graph Theory

Hitting every large maximal clique with a stable set ★★

Author(s): King; Rabern

Conjecture   There is a universal constant $ \epsilon>0 $ such that every graph contains a stable set which intersects every maximal clique of size $ (1-\epsilon)(\Delta+1) $.

Conjecture   Every graph contains a stable set which intersects every maximal clique of size $ >\frac{2}{3}(\Delta+1) $.

Keywords: independent set; maximal clique

Posted by Andrew King
updated March 31st, 2011
add new comment
Combinatorics » Matroid Theory

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

Conjecture   If $ M_1,\ldots,M_k $ are matroids on $ E $ and $ \sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1) $ for every partition $ \{X_1,\ldots,X_k\} $ of $ E $, then there exists $ X \subseteq E $ with $ |X| = \ell $ which is independent in every $ M_i $.

Keywords: independent set; matroid; partition

Posted by mdevos
updated June 11th, 2007
add new comment
Syndicate content