Combinatorics » Ramsey Theory

The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture   If $ A $ is 2-large, then $ A $ is large.

Keywords: 2-large sets; large sets

Posted by vjungic
updated June 10th, 2007
add new comment
Graph Theory » Algebraic G.T.

Ramsey properties of Cayley graphs ★★★

Author(s): Alon

Conjecture   There exists a fixed constant $ c $ so that every abelian group $ G $ has a subset $ S \subseteq G $ with $ -S = S $ so that the Cayley graph $ {\mathit Cayley}(G,S) $ has no clique or independent set of size $ > c \log |G| $.

Keywords: Cayley graph; Ramsey number

Posted by mdevos
updated June 10th, 2007
add new comment
Combinatorics » Matroid Theory

Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let $ G $ be an (additive) abelian group, and for every $ S \subseteq G $ let $ {\mathit stab}(S) = \{ g \in G : g + S = S \} $.

Conjecture   Let $ M $ be a matroid on $ E $, let $ w : E \rightarrow G $ be a map, put $ S = \{ \sum_{b \in B} w(b) : B \mbox{ is a base} \} $ and $ H = {\mathit stab}(S) $. Then $$|S| \ge |H| \left( 1 - rk(M) + \sum_{Q \in G/H} rk(w^{-1}(Q)) \right).$$

Keywords: matroid; sumset; zero sum

Posted by mdevos
updated June 10th, 2007
add new comment