Title: The structure of claw-free graphs

A graph is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph K1,3. The most well-known class of claw-free graphs is the class of line-graphs, but there are some claw-free graphs that are far from being line-graphs, such as the Schlafli graph. We prove that every claw-free graph can be built by simple constructions from line graphs, induced subgraphs of the Schlafli graph, and some other simple basic graphs. This is joint work with Paul Seymour.

Title: Quantum Algorithms

I will talk about two problems where quantum computation has an exponential speedup over the best known classical algorithm. The first is Pell's equation, a very old number theory problem, and the second is the shifted Legendre symbol problem, which is an oracle problem related to cryptography.

Title: Tumbleweeds and the Extra Edge Paradox

A positional game is a two-player game where the players alternately occupy vertices of a hypergraph. The winning lines of the game are the (hyper)edges of the hypergraph. For example, the underlying hypergraph for the Tic-tac-toe game has nine vertices and eight edges. There is an interesting phenomenon that may occur in positional games. There exists hypergraphs H such that Player 1 has a winning strategy on H, but if you add a particular edge to H, then Player 2 can force a draw on this modified hypergraph. We call this the Extra Edge Paradox. The only previous known examples of the Extra Edge Paradox occurred in non-uniform hypergraphs. We will introduce a class of hypergraphs called tumbleweeds and show a 4-uniform example of the Extra Edge Paradox, which is a modified tumbleweed.

Title: Crowding effects promote coexistence in the chemostat

The chemostat is a model for a biological reactor in which several species are competing for nutrient. Typically, the 'competitive exclusion principle' applies, implying that at most one of the species survives in the long run. In this talk we take crowding effects- which are usually neglected - into account and investigate the resulting chemostat from a feedback perspective. This perspective is useful because it allows application of a small gain theorem that leads to global stability results. In addition we show that coexistence is possible if crowding effects are large enough, contrasting the competitive exclusion principle.

The proof techniques are based on recent developments for monotone input output systems. Many other biological systems seem to fall within this framework. If time permits we will give two more examples: a generalized predator-prey system and mitogen activated protein kinase (MAPK) cascades. In both examples oscillations can occur, at least theoretically. Obviously one would like to know when they can be ruled out. The feedback perspective proposed here, in conjuction with the small gain theorem, provide an answer to this question.

Title: Computational functional genomics: getting from high-throughput data to accurate information in biology

Microarray analysis allows for large-scale exploration of gene expression by taking a snap shot of the cell at a specific point in time. Such datasets may provide insight into fundamental biological questions as well as address clinical issues such as diagnosis and therapy selection. The resulting data are complex and challenging to analyze without sophisticated computational tools. This talk will highlight the issue of improving the specificity of biological signal detection from microarray data. I will present robust and accurate algorithms for missing value estimation for microarray data and for identification of differentially expressed genes from gene expression datasets. This talk will also address gene function prediction and present a Bayesian framework for integrated analysis of gene expression data with datasets from other high-throughput biological data sources.

Title: Counting/Enumerating Spanning Trees in (di-) Graph

We summarize the recent results about counting/enumerating the number of spanning trees in a graph or a digraph (where multiple edges and self-loops are permitted). A spanning tree in a graph $G$ is a tree that has the same vertex set as $G$. An oriented spanning tree in a digraph $D$ is a rooted tree with the same vertex set as $D$ in which there is a node specified as root, from the root there is a path to any of vertices of $D$. The network reliability is determined, basically, by the number of spanning trees of its graph. Recently, much research about the number of spanning trees is devoted to determining the exact formulae for the numbers in special graphs. In this talk we first describe, combinatorically and algebraically, the general methods for counting the number of spanning trees in a (di-)graph. We then exam these methods to determine the formulae of the numbers of spanning trees in circulant graphs, composite graphs, etc. We provide formulae for the numbers of spanning trees in circulant (di-)graphs and (di-)graphs and the asymptotic properties of these numbers.