Course outline: 

1) Independent sets from the combinatorial point of view.
 

• Extremal combinatorics is certainly the first field in which maximum independent sets is widely studied, with Turan and Ramsey theorem. The main idea here is to study how α(G) is influenced by other parameters such as the clique number or the number of edges. This domain was extremely influencial in the development of discrete probabilities. We will review some probabilistic techniques.
• From the optimization point of view, a question arose when considering for which graphs maximum independent set could be well characterized. It appeared that bipartite graphs, their complements, their line graphs and complements are well-behaved, and Berge proposed its celebrated class of perfect graphs encompassing all of these properties. From a polyhedral point of view, the polytope of independent sets of a perfect graph is characterized by the so-called clique constraints, and from the structural point of view, perfect graphs avoid odd induced cycles and their complements. Remarkably, the converse holds and is known as "The strong perfect graph theorem". In this part some tools of polyhedral methods and graph decompositions (à la Berge) will be explored.
• As independent sets are too complex in the general case, we will restrict ourselves to specific classes of graphs (closed w.r.t. induced subgraphs), or equivalently graphs avoiding some specific substructures. One of the most classical restriction one can impose on graphs concerns its cycles (think of bipartite graphs for instance as avoiding odd cycles). Remarkably, computing alpha is easy (or at least easier) when forbidding disjoint cycles (with or without parity constraints). The tools here are surprisingly diverse, like Erdos-Posa property, but also width-parameters such as tree-width. A particularly nice feature here is that geometrical problems can often be translated into restricted graph classes and solved in this context.

2) Independent sets from the computational point of view.

 

• The computation of alpha is hard to approximate (PCP theorem) for general graphs. We will restrict ourselves to classes in which either we can reach an exact solution, or at least get some fixed constant approximation or some PTAS. We will also investigate the parameterized complexity landscape of computing α. We will review here a very large diversity of algorithm paradigms, even though dynamic programming will certainly be our best pick.
• Linear and semi-definite optimization are also very useful tools in this field. Using SDP for instance, the independence number of a perfect graph can be computed by the Lovasz theta function, computed on its edge-complement (and no known combinatorial algorithm is known). Furthermore, SDP is the main tool for the Shannon capacity of a graph G (that is the asymptotic independence number of the powers of G).