Master Parisien de Recherche en Informatique 2-29-1 III/III J.-S. Sereni Matchings in Graphs 11/2009 Some Definitions

We just give the definitions and characterisations needed. More background can be found in the treatise by Schrijver [4, Chapter 5]. A convex combination of the vectors x1,..., xk ∈ Rn is a vector equal to ∑k i=1 λixi where λ1,..., λk ∈ R+ with ∑k i=1 λi = 1. A set C ⊆ Rn is convex if for every x, x ′ ∈ C and every λ ∈ [0, 1], it holds that λx + (1 − λ)y ∈ C. The convex hull conv. hull(X) of a set X ⊆ Rn is the smallest convex set that contains X, that is{ λ1x1 +...+ λnxn: n ∈ N, ∀i ∈ {1,..., n}, xi ∈ X and λi ∈ R+,