independent set


The Double Cap Conjecture ★★

Author(s): Kalai

\begin{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. \end{conjecture}

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

Hitting every large maximal clique with a stable set ★★

Author(s): King; Rabern

\begin{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)$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

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

Keywords: independent set; maximal clique

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

\begin{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$. \end{conjecture}

Keywords: independent set; matroid; partition

Syndicate content