TITLE: Fault Tolerance in Protein Interaction Networks: Stable Bipartite Subgraphs and Redundant Pathways

ABSTRACTS:

As increasing amounts of high-throughput data for the yeast interactome becomes available, more system-wide properties are uncovered. One interesting question concerns the fault tolerance of protein interaction networks: whether there exist alternative pathways that can perform some required function if a gene essential to the main mechanism is defective, absent or suppressed. One signature pattern for redundant pathways is the BPM (between-pathway model) motif, first suggested by Kelley and Ideker. Past methods proposed to search for BPM motifs have had several important limitations. First, they have been driven heuristically by local greedy searches, which can lead to the inclusion of extra genes that may not belong in the motif; second, they have been validated solely by functional coherence of the putative pathways using GO enrichment, making it difficult to evaluate putative BPMs in the absence of already known biological annotation.

We show how a simple "folk" theorem in graph theory (probably due to Erdos) can help us identify possible BPMs in such a way that not only do we get better coherence of biological function, but we also have a direct way to validate our results based directly on the structure of the network. We uncover some interesting biological examples of previously unknown putative redundant pathways in such areas as vesicle-mediated transport and DNA repair.

TITLE: Cliques

ABSTRACTS

Some dull results and interesting problems inspired by the (easy) question: what is the minimum number of (maximal) cliques in an n-vertex graph and its complement? The answer to that question is n + 1; the minimizing graphs were characterized in my first paper on graph theory, a joint work with M. M. Krieger. We get nontrivial questions by changing "graph" to "hypergraph", or by changing "an n-vertex graph and its complement" to "an edge decomposition of the complete graph on n vertices into k spanning subgraphs". Some partial results on these questions are obtained in my posthumous paper with P. Erdos and M. M. Krieger.

TITLE: Venn Diagrams, Necklaces, and Chain Decompositions of Posets

ABSTRACTS

TITLE: A survey of knot theory and its combinatorial invariants

ABSTRACTS:

I will give a brief introduction to the field of knot theory and discuss some recent combinatorial invariants of knots. In particular, I will discuss some invariants of knots that are related to graphs and outline the construction of the influential combinatorial knot Floer homology defined recently by C. Manolescu, P. Ozsvath, and S. Sarkar.

TITLE: Binomial Primary Decomposition

ABSTRACTS:

Primary decomposition is the analog of prime factorization for ideals in the polynomial ring. In the case of binomial ideals, i.e. ideals that are generated by polynomials with at most two terms, primary decomposition ends up being controlled by combinatorial structures generalizing graphs. I will illustrate this with examples, where the problem translates into finding the bounded connected components of a graph with infinitely many vertices. This talk is based on joint work with Alicia Dickenstein and Ezra Miller.

TITLE: Graph Coloring Problems Related to the Four-Color Theorem

ABSTRACTS: This talk will sketch out some major problems related to the four-color theorem of Haken, Appel and Koch. These include (1) reducing dependency on the computer in the proof of the theorem, (2) conjectures derived from the Kempe approach through vertex colorations such as the Hadwiger conjecture and the two open cases of the Hajos conjecture, and (3) conjectures related to the Tait approach through facial colorations such as Tutte's flow conjectures and the edge-coloration conjectures of Gupta, Goldberg and Seymour.

TITLE: Lattice Points and Kindly Chess Queens

ABSTRACTS:

In how many ways can q queens be placed on an n × n chessboard so no two queens attack each other? What about other chess pieces, like bishops or nightriders (a fairy chess piece)? These questions generalize the famous Eight Queens Problem, which asks for the number of ways to place 8 nonattacking queens on an 8 × 8 chessboard, to any number of identical pieces on any sized square board.

Seth Chaiken, Chris Hanusa, and I treat the questions by means of a generalization of Ehrhart's theory of counting lattice points in a convex polytope. For a chess piece whose moves are unlimited, like those of a queen, rook, or bishop but not a king or knight, a nonattacking configuration corresponds to a 1/t-fractional point in the 2q-dimensional unit hypercube that is not in any of certain hyperplanes that depend on the moves. The number of such points, by Beck's and my theory of inside-out polytopes, is a function of t that is given by a cyclically repeating series of p polynomials of degree 2q. The number N_q(n) of nonattacking configurations, as a function of n, is therefore also given by a cyclically repeating series of polynomials.

To get N_q(n) exactly (unless q is tiny) one needs an upper bound for p. One bound is the least common multiple of the subdeterminants of the Kronecker product of the move matrix with the incidence matrix of a complete graph. That can be computed by a complicated formula.