ANNE BERGERON, UQAM
The combinatorial beauty of genome evolution  [PDF]

Genomes evolve through a range of edit operations, some of them effecting small local changes, while others move big chunks of genetic material in cut-and-paste operations that scramble the linear order of the chromosome. In this talk, we will present various mathematical models that try to reconstruct the history of these rearrangements. The basic problem, called the Sorting Problem, is to compute the minimal number of operations that transform a genome into another. This problem has many variants depending on the set of allowed operations, and the solution for the most common variant relies on a deep understanding of the architecture of permutations and associated graphs. We will present these structures together with many examples from the genomes of mammals, insects and plants. We will also give an elementary derivation of the solution for a variant that allows all operations that require at most two cuts in a genome. The answer to the Sorting Problem is often not sufficient, since, from an evolutionary point of view, we also want to reconstruct plausible ancestors of existing species: this yields surprising connections to combinatorial objects such as matrices with the consecutive ones property, non-crossing partitions and parking functions. These topics merely scratch the surface of evolutionary history. Indeed, each time biologists turn their sequencing machines onto a few more of the millions of species that populate the planet, we discover new patterns and new mechanisms whose mathematical modelling will provide ever new fascinating problems.

SARA BILLEY, University of Washington
An introduction to $k$-Schur functions and QSYM  [PDF]

Historically, the Schur functions have been an important basis of the ring of symmetric functions. About 10 years ago, Lascoux, Lapointe and Morse introduced a new analog of Schur functions which they call $k$-Schur functions. There are many interesting connections between the $k$-Schur functions, Schubert varieties, Gromov-Witten invariants, affine Grassmannians, and tableaux combinatorics. For example, Lam showed that these elements represent Schubert classes in the cohomology ring of the affine Grassmannian when the indeterminate $t=1$. It is conjectured that the Macdonald polynomials expand positively into the basis of $k$-Schurs for certain $k$. In this talk, we will give a natural defintion of $k$-Schur functions as a quasisymmetric function and discuss the final step toward proving that the $k$-Schur functions are Schur postive via a computer proof and Assaf's $D$-graph machinery. The required computation is a halting problem with a termination condition but no upper bound on the number of steps required to stop. This is joint work with Sami Assaf.

ALLAN BORODIN, University of Toronto
When is it good to be greedy (in algorithm design)  [PDF]

Greedy algorithms provide a conceptually simple approach to solving search and optimization problems. These natural algorithms have been analyzed for over 50 years and yet we are still seeing new applications as well as more generous ideas as to what it means to be greedy. We will survey some of the history and suggest how greedy algorithm design is being applied in algorithmic mechanism design and social network studies in addition to traditional combinatorial optimization.

CHANDRA CHEKURI, University of Illinois at Urbana-Champaign
Submodular set function maximization via the multilinear relaxation and dependent randomized rounding  [PDF]

A real-valued set function $f:2^N\rightarrow R$ on a finite ground set $N$ is submodular iff $f(A) + f(B) \ge f(A \cap B) + f(A \cup B)$ for all $A, B \subseteq N$. Submodularity is an important property in combinatorial optimization, and has long been utilized to derive structural insights and efficient algorithms. In this talk we consider the problem of finding a set $S \subseteq N$ that maximizes a given non-negative submodular function $f$ subject to a variety of independence constraints on $S$. This problem is NP-Hard even under very restricted settings so we consider polynomial-time approximation algorithms.

The work of Cornuejols, Fisher, Nemhauser and Wolsey from the late 70's considered greedy and local-search methods when $f$ is a monotone (non-decreasing) submodular function. More recently these methods have been augmented and improved, and have also been applied to non-monotone functions. This talk will focus on a new approach that is based on (approximately) solving a non-linear continuous extension of $f$ called the multilinear extension, and rounding the resulting fractional solution via dependent randomized-rounding techniques. The talk will describe some algorithmic results that follow from this approach.

JACOB FOX, MIT
Intersection Graphs, Drawings, Posets, and Separators  [PDF]

A string graph is an intersection graph of arcwise connected sets in the plane. The study of these graphs was originally motivated about a half-century ago by applications to the study of genetic structures and electrical networks. In this talk, I will describe a surprisingly strong connection between string graphs and posets. In combination with new separator theorems for string graphs, these tools allow us to make progress on a number of fundamental algorithmic, extremal, and enumerative problems for intersection graphs and graph drawings. This talk is based on joint work with Janos Pach.

JEFF KAHN, Rutgers
Thresholds and expectation thresholds  [PDF]

The understanding of thresholds is a central issue in probabilistic combinatorics and elsewhere. (An {\em increasing property}, say $\cal F$, is a superset-closed family of subsets of some (here finite) set $S$; the {\em threshold question} for $F$ asks (roughly), about how many random elements of $S$ should one choose to make it likely that the resulting set lies in $\cal F$? For example: about how many random edges from the complete graph $K_n$ are typically required to produce a Hamiltonian cycle?)

A ludicrously general conjecture of G. Kalai and the speaker says something to the effect that there is {\em always} (i.e. for any $\cal F$) a pretty good naive explanation for the threshold being what it is. We'll make this precise and discuss a few recent results that, while of considerable interest in their own right, are also merely {\em examples} of the conjecture.

ALICE SILVERBERG, University of California, Irvine
Counting points on elliptic curves, from Gauss to the present  [PDF]

In his Disquisitiones Arithmeticae, Gauss published a simple formula for the number of solutions mod $p$ to $x^3 - y^3 = 1$. In his last diary entry, Gauss gave a similar result for the number of solutions mod $p$ to $x^2 + y^2 + x^2y^2 = 1$. In modern language, these results can be viewed as part of an extensive history of counting points on elliptic curves over finite fields, which now has applications to cryptography. This talk will discuss some of this history.

STEPHAN THOMASSE, Université Montpellier 2
Applications of VC-dimension for Graphs and Hypergraphs  [PDF]

The Vapnik-Cervonenkis-dimension of a hypergraph $H$ is a measure of its complexity. When this parameter is bounded, the transversality of $H$ is bounded in terms of its fractional transversality. This provides a nice tool for graphs, when interpreting neighborhoods as hyperedges. I will survey some results on domination, coloring and Erd{\H o}s-P\'osa-property in which the VC-dimension-approach gives short proofs and rather sharp bounds. I will conclude on some problems where VC-theory seems the right approach.

Handling of online submissions has been provided by the CMS.