COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
Date  Place  Time  Speaker  Abbreviated Title 

Sept. 23  EOW 430  2:30  Brian Alspach  Time Constrained Searching and Sweeping 
Oct. 7  EOW 430  2:30  Aaron Williams  Packing Directed Cycle Covers 
Oct. 14  EOW 430  2:30  Wendy Myrvold  Generating Small Combinatorial Objects 
Oct. 21  EOW 430  2:30  Lior Malka  ZeroKnowledge Proofs for Graph Isomorphism 
Oct. 28  Cle A 203  2:30  Stephen Beneke  An Open Problem in Classical Domination Theory 
Nov. 4  EOW 430  2:30  Venkatesh Srinivasan  Dinur's Proof of the PCP Theorem 
Nov. 11  _  _  No CAG.  Reading Break 
Nov. 18  _  _  No CAG.  Combinatorial Potlatch in Seattle 
Nov. 25  Cle A 203  2:30  Baogang Xu  Some Results and Problems Related to 3Coloring of Plane Graphs 
Dec. 2  EOW 430  2:30  Ruskey/Daugherty  CMS Conference Practice Talks: I 
Dec. 9  EOW 430  2:30  Fowler/Myrvold  CMS Conference Practice Talks: II 
Tues. Dec. 13  EOW 430  10:30  Natasa Przulj  Analyzing Large Biological Networks: ProteinProtein Interaction Example 
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_{5}e as a minor (K_{5}e is the complete graph on five vertices with a single edge removed). This result can be seen as best possible since forbidding K_{5} 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.
ZeroKnowledge is a complexity class, just like P, and NP. However, unlike P and NP, which are formally defined using the notion of Turing machines, ZeroKnowledge 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_{0} is isomorphic to G_{1}". That is, given graphs G_{0} and G_{1}:
This is what ZeroKnowledge 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 ZeroKnowledge Proof Systems. J. ACM 38(3): 691729 (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_{3} 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 5circuits is 3colorable. 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 3colorable? 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 usersupplied 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.
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 VS 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 allcarbon molecule C_{n}, is cubic, with only pentagonal and hexagonal faces (12 and n/210, 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 clososeries of borane anions, B_{N}H_{N}^{2}. A construction for (infinite) families of cospectral fullerene duals will be presented.
An independent set of a graph G is a set of vertices of G which are pairwise nonadjacent. 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 120cell. 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 proteinprotein interactions (PPIs) will be an integral part of this understanding. Our approach is to focus on the largescale 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 wetlab 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.