Plenary Talks

Joint work with M. H. de Carvalho and U. S. R. Murty.


An Order Theoretic Approach to Union Closed Set Systems
Speaker:  Dwight Duffus (Tuesday, 8:30 - 9:30)
Chair: Sulamita Klein

The union-closed set system conjecture, which appears to have been formulated by Peter Frankl in the 1970's, is that any nontrivial such system has an element in at least half the sets. There is an easy translation, made independently by several researchers, into statements about lattices. Attempts to solve the conjecture in this order theoretic context have led, not surprisingly, to partial results for special classes of lattices. The lattice theory viewpoint also suggests several approaches to the problem and some interesting variants on the original conjecture. In this talk, partial results and related conjectures, obtained with Bill Sands [University of Calgary], are presented, as well as an experimental results, done with Bob Roth [Emory University].


Certificates and Graph Algorithms
Speaker:  Jeremy Spinrad (Tuesday, 9:30 - 10:30)
Chair: Sulamita Klein

The notion of a certificate for a property, which is due to Edmonds, arises frequently in complexity theory. A certificate is a proof that a property holds, and the length of a certificate may be much shorter than the time needed to find such a certificate. This talk will discuss three different areas of graph algorithms, in which certificates have played crucial roles. The first is the notion of a robust algorithm. A robust algorithm to solve a problem on a class of inputs must solve the problem correctly if the input is in the class, and if the input is not in the class may either solve the problem correctly or answer that the input is not valid. The second type of problem related to certificates involves using matrix multiplication to improve asymptotic running times of algorithms. Matrix multiplication is used to improve time bounds for such problems as finding minimal fill, two-pairs, asteroidal triples, and a variety of other problems on graphs. A third area where certificates arise is a certifying algorithm, which is required to produce output such that the answer is ``easy'' to verify.



Random Walks on Random Graphs
Speaker:  Alan M. Frieze (Tuesday, 18:00 - 19:00)
Chair: Bruce A. Reed

We give tight estimates for the cover time of random graphs and random regular graphs. We also give estimates for the number of vertices visited in a random walk on a randomly growing ``web-graph''. This is joint work with Colin Cooper.


Social Networks: Algorithms and Applications
Speaker:  Prabhakar Raghavan (Wednesday, 8:30 - 9:30)
Chair: Yoshiko Wakabayashi

Beginning with Milgram's classic ``six degrees of separation'' experiments in the 1960's, social network theory has evolved to study how individuals interact and disseminate information. More recently, the study has come to encompass the broader network involving people as well as the documents and information they interact with---examples include recommendation systems and the use of link analysis in web search engines. This talk will provide an overview of this evolving area and the many research problems that arise, including issues in privacy protection.


On Two Generalizations of Split Graphs
Speaker:  Jayme L. Szwarcfiter (Wednesday, 9:30 - 10:30)
Chair: Yoshiko Wakabayashi

A graph G is a split graph when V(G) can be partitioned into a clique and an independent set. They form a very well known class of graphs, introduced about 35 years ago. In this talk we consider two generalizations of split graphs, namely starlike graphs and generalized split graphs. The former corresponds to the intersection graphs of substars of a star, while the latter class can be defined as follows. Say that a graph G is clique-split when V(G) can be partitioned into cliques C,C_1,\dots,C_k, such that no two vertices belonging to distinct cliques C_i, C_j are adjacent. Say that G is a generalized split graph when G or its complement is clique-split. Starlike graphs were introduced in the context of the pathwidth problem, while generalized split graphs were defined in the probabilistic study of perfect graphs. We describe different characterizations for starlike graphs, including one by forbidden subgraphs. For generalized split graphs, we formulate a characterization and a polynomial time recognition algorithm. Starlike graphs form a simple generalization of split graphs, and generalized split graphs extend starlike graphs, in a natural way. The work on starlike graphs has been done jointly with Márcia Cerioli, while on generalized split graphs, with Frédéric Maffray.


Brambles and Excluded Minors
Speaker:  Bruce A. Reed (Thursday, 8:30 - 9:30)
Chair: Cristina G. Fernandes

After defining and motivating the concept of brambles, we shall discuss recent work on the tree-width of graphs without large prisms and of graphs without small grids.


Adaptive Sampling for Quickselect
Speaker:  Alfredo Viola (Thursday, 9:30 - 10:30)
Chair: Critina G. Fernandes

The median-of-3 variant of quickselect has been largely studied. However, the following natural adaptive variant had not been analyzed: ``choose as pivot the smallest of the sample if the rank of the sought element is small, the largest if the rank is large, and the median if the rank is medium''. We first analyze proportional-of-2 and proportional-of-3 in which we use equal-size intervals. We propose \nu-find, a generalization of median-of-3 and proportional-of-3 with interval breakpoints \nu and 1-\nu. We give the optimal \nu and values for which \nu-find outperforms median-of-3. The talk will be concentrated in the algorithmic aspects of the problem, as well as how its analysis contributes to the understanding of the most delicate parts of them. This is joint work with Conrado Martínez and Daniel Panario.


Components and Primes
Speaker:  Bruce Richmond
Chair: Daniel Panario (Thursday, 18:00 - 19:00)

There is an analogy between the prime factors of the first n integers and the components of combinatorial objects of size n. The objects may be permutations which may be factored into cycles. The objects may be polynomials over a finite field which can be factored into into irreducible polynomials. The unique factorization gives an analogy between generating functions but more is true. The probability that the first n integers have largest prime factor <= m is asymptotic to the Dickman function evaluated at log(n)/log(m) for m sufficiently small compared to n. The probability that the smallest prime factor of the first n integers is >= m is asymptotic to the Buchstab function evaluated at log(n)/log(m) divided by log(m). We can obtain the corresponding probabilities for combinatorial objects by replacing log(n) and log(m) by n and m. This was pointed out by Billingsley (1972) and Knuth and Trabb-Pardo (1976). Gourdon established this analogy for the largest component using the Flajolet-Odlyzko singularity analysis for general classes of combinatorial objects. Panario and Richmond followed with the analogy for the smallest component. Recently the Buchstab and Dickman original recursive arguments have been adapted to combinatorial objects by Bender, Mashatan, Panario and Richmond. When the objects are 2-regular graphs new Buchstab and Dickman functions arise. These results will be surveyed.


String Matching for Music
Speaker:  Esko Ukkonen (Friday, 11:30 - 12:30)
Chair: Marie-France Sagot

Computer-aided retrieval and analysis of music offers fascinating novel challenges for pattern matching research. The standard writing of music uses notes, giving the pitch and duration of each tone. As the pitch levels and durations are limited to a relatively small set of discrete values, we in fact have a sequence of discrete symbols - a natural domain for combinatorial pattern matching. The talk considers transposition invariance in string matching, motivated by music retrieval. Transposition invariance can be achieved both in the exact and in the approximate string matching with relatively small extra effort. We also consider the related problem of geometric point pattern matching under translations and discuss how the periodicity of the pattern can be utilized.

This is joint work with K. Lemstrom, V. Makinen and G. Navarro.