COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2005

Attempting to capture an intruder in a graph when the intruder may be located at vertices or along edges is known as sweeping. When the intruder may be located only at vertices, the process is known as searching. I shall discuss several models for searching and sweeping. I'll then move to some new work on searching and sweeping when there are time constraints present.

In a directed graph, a directed cycle cover is a set of arcs that intersects every directed cycle. The maximum number of disjoint cycle covers is less than or equal to the minimum length of a directed cycle. In this talk, we show that equality always holds when the underlying undirected graph does not have K₅-e as a minor (K₅-e is the complete graph on five vertices with a single edge removed). This result can be seen as best possible since forbidding K₅ as a minor does not guarantee equality.

When making conjectures about combinatorial objects (e.g. graphs, trees, Latin squares, planar graphs) it is often helpful to have access to all of the small objects in the class. A standard tactic for generating exactly one object in each isomorphism class is a parent/child generation scheme. In this talk, we discuss the general methodology plus also computational techniques for making the generation process faster.

Zero-Knowledge is a complexity class, just like P, and NP. However, unlike P and NP, which are formally defined using the notion of Turing machines, Zero-Knowledge is defined using the notion of two parties: an all powerful "Prover" and an efficient algorithm called "the Verifier". Why define a complexity class so awkwardly? Cryptography!!!

In this talk, I will show how the prover P can convince the verifier V of the truth of the assertion "graph G₀ is isomorphic to G₁". That is, given graphs G₀ and G₁:

1. If G₀ and G₁ are isomorphic, then P can prove it to V, and V accepts the assertion "G₀ is isomorphic to G₁" as true.
2. If G₀ and G₁ are not isomorphic, then no matter what P does, he is unlikely to convince V that the assertion "G₀ is isomorphic to G₁" is true. And the most amazing thing is that:
3. The verifier learns nothing but the fact that the assertion is true (that is, in (1) the verifier is both convinced AND learns nothing else).

This is what Zero-Knowledge is about: how to convince the verifier that an assertion is true, without giving up any information. The material in this talk is taken from: Oded Goldreich, Silvio Micali, and Avi Wigderson, Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM 38(3): 691-729 (1991).

The domination number of a graph G, denoted gamma(G), is the minimum cardinality of a dominating set of G. Let n and delta denote the order and minimum degree of G respectively. An interesting open problem in classical domination theory today is whether gamma(G) <= ceiling(n/3) for graphs G with delta >= 3. In 1985, Cockayne, Ko and Shepherd proved that this is true for all graphs that do not contain K_1,3 or the corona of K₃ as an induced subgraph. McCuaig and Shepherd showed in 1989 that gamma(G) <= 2n/5 for all graphs with delta >=2, with the exception of 7 (small) graphs. In 1996, Reed considered graphs with delta >= 3 and showed that gamma(G) <= 3n/8. He conjectured that gamma(G) <= ceiling(n/3) for all cubic graphs. In a recent paper, Kostochka and Stodolsky provided a counterexample to Reed's conjecture. The results of their paper will be discussed during this talk.

Probablistically Checkable Proofs (PCPs) are NP witnesses that allow efficient probabilistic verification based on probing few bits of the NP witness. The celebrated PCP theorem (proved by Arora, Safra and Arora, Lund, Motwani, Sudan, Szegedy) asserts that NP languages have short PCPs that can be verified efficently by a verifier probing only constant number of bits in the proof. This theorem gives a new characterization of NP. PCP theorem is useful for its connections to inapproximability results and has applications in coding theory and in cryptography. In spite of the importance of PCP theorem, the original proof is quite long and very algebraic in nature. In this talk we will discuss a recent result of Dinur that gives a simpler proof of this theorem. The proof is combinatorial in flavor and uses walks on expander graphs.

In 1976, Steinberg proposed a conjecture that says every plane graph without 4- and 5-circuits is 3-colorable. This conjecture is still open. In the earlier of 1960s, Havel proposed a question as follow: Is there an integer n such that every plane graph without triangles of distance less than n is 3-colorable? We only know now that if such an n does exist, then n >= 4.

In this talk, we will present some results related to these two questions.

In this talk we will describe a couple of web sites produced by the author that have proved popular with teachers of mathematics at the secondary school and college levels for the teaching of various topics in discrete mathematics. The "Combinatorial Object Server" (COS) will produce exhaustive lists of discrete structures such as permutations, combinations, trees, solutions to pentomino puzzles, and so on, based on user-supplied input parameters. The "Amazing Mathematical Object Server" is similar but more oriented to younger students. We will describe the philosophy, capabilities, and underlying technology of these web sites.

Exploring the Influence and Total Influence Numbers of a Graph
Sean Daugherty
Friday Dec. 2, 2:30pm, EOW 430

Recently, the study of social networks has given rise to a graph parameter known as the influence number: eta(G). This parameter measures the influence that a vertex subset S has on the remaining vertices such that each vertex not in S is influenced by the closest member of S as follows: eta(S) equals the sum over all vertices u not in S of 1/[2^d(u, S)]. The influence number of a graph G, eta(G), is the maximum value of eta(S) where S is a subset of V.

A natural extension to the influence number allows each vertex not in S to be influenced by every vertex in S. This gives the total influence number, eta_T(G), which is equal to the maximum over all subsets S of V of the sum over all pairs v, u where v is in S and u is in V-S of 1/[2^d(u, v)].

Other applications include facility location problems where the quality of service decays exponentially with respect to distance. This talk will explore some of the basic results involving the influence and total influence numbers of a graph.

A fullerene polyhedron, representing an all-carbon molecule C_n, is cubic, with only pentagonal and hexagonal faces (12 and n/2-10, respectively, by Euler's theorem). The spectrum of the adjacency matrix contains a great deal of qualitative chemical information on optimum electron count, electronic configuration, stability and reactivity of the molecule. Connections between graph theory and these chemical models will be discussed. Cospectral fullerene graphs would be of interest as representing molecules with structures that were different but with (some) identical properties. As yet, no cospectral fullerenes are known, but many pairs of fullerenes with cospectral duals have now been found (P. W. Fowler and M. Duncan, to be published). The dual of a fullerene graph is also a polyhedral graph, having all faces triangular, 12 vertices of degree 5 and all others of degree 6; considered as the skeleton of a molecule, it is a model for large boron hydrides, based on extrapolation of the known closo-series of borane anions, B_NH_N^2-. A construction for (infinite) families of cospectral fullerene duals will be presented.

Fast Enumeration of All Independent Sets of a Graph
Wendy Myrvold,
Friday Dec. 9, 2:30pm, EOW 430

An independent set of a graph G is a set of vertices of G which are pairwise non-adjacent. There are many applications for which the input is a graph G with a large symmetry group and the goal is to generate either all of the independent sets or all of the maximum independent sets up to isomorphism. We present a very fast practical algorithm for this problem. The tactic can also be applied to many other problems: some examples are generation of all colourings or matchings of a graph up to isomorphism. Two applications are given to illustrate the utility of this algorithm- finding all independent sets of the C60 and C70 fullerenes, and also the problem of finding a maximum set of vertices at distance four or more in the 120-cell. This is joint work with Patrick Fowler.

Understanding the inner workings of the cell constitutes one of the foremost fundamental problem of modern biology. Since most cellular processes involve interactions between the thousands of different proteins present in the cell, understanding protein-protein interactions (PPIs) will be an integral part of this understanding. Our approach is to focus on the large-scale properties of the cell's PPI network. The PPI network simply describes which pairs of proteins interact, represented as a graph. Since gathering the raw data of which proteins interact with each other is an ongoing expensive process, it is important to have a model of PPI networks that can adequately guide wet-lab experiments.

We analyze the local structural properties of existing, known PPI networks using a novel tool that exhaustively counts frequencies of small connected subgraphs over an entire graph. We demonstrate that existing models of PPI networks do not fit the data under this measure, and propose a new, geometric random graph model of PPI networks that fits the data significantly better than existing models.

Since counting subgraphs of large graphs is computationally intensive, we propose two heuristics for uncovering local structure of PPI networks and demonstrate that the heuristics work well on real data.