Spring 2004 Archive

Feb. 6: Ryan Martin, On the editing distance in graphs, Part II

Given a family of graphs Γ, the editing distance of a graph G from Γ is the number of combined deletions and additions of edges so that the resulting graph is in Γ. In this talk, we fix a graph H and consider Forb(H), the set of graphs that have no induced copy of H. We provide bounds for the maximum editing distance among all n-vertex graphs from Γ=Forb(H). In doing so, we also introduce a graph invariant which we call the binary chromatic number.

We continue the work in the previous talk, using Szemerédi's regularity lemma to give asymptotic bounds for the editing distance. These bounds are tight for many values of H, in particular when H is self-complementary. (Return to top.)

Feb. 13: Dan Ashlock, Edit Metric Error Correction

In the course of a bioinformatics project, a need arose to be able to read short stretches of DNA and then correct sequencing errors in the output of the DNA sequencer. The problem is the classical one of using a noisy channel to transmit information but the types of errors that appear are not classical. A DNA sequencer can not only perform substitutions of letters but may skip or duplicate bases. The key difficulty in error correction in DNA is that that the natural metric for errors is the edit distance. The edit distance between two strings is the minimum number of single letter insertions, deletions, and substitutions that transform one string into another. The edit metric is a good deal messier than the Hamming metric of classical error correcting codes.

This talk will cover the biological motivation for DNA error correction, remind the audience of the definitions of the classical theory of error correcting codes, generalize the problem to error correction in the Edit metric, and then introduce an ad hoc computational method generalizing Conway's lexicode algorithm for locating large DNA error correcting codes. Open problems will be given. (Return to top.)

Feb. 20: Leslie Hogben, Minimum path covers for trees, part I

Abstract TBA. (Return to top.)

Feb. 27: Leslie Hogben, Minimum path covers for trees, part II

Abstract TBA. (Return to top.)

Mar. 5: Sung-Yell Song, Characterization of regular digraphs

I will speak about a specific class of digraphs, called "doubly-regular (m, r)-team tournaments" and discuss some characterization results on this type of digraphs. The method employed in the characterization is standard techniques often used in algebraic graph theory. See the presentation slides. (Return to top.)

Mar. 26: Stephen J. Willson, Building supertrees using distances, part I

Suppose that a family of rooted phylogenetic trees T_i with different sets X_i of leaves is given. A supertree for the family would be a single rooted tree T whose leaf set is the union of all the X_i, such that the branching information in T corresponds to the branching information in all the trees T_i. This paper proposes a polynomial-time method BUILD-WITH-DISTANCES that makes essential use of distance information provided on the trees T_i to construct a rooted tree T. When a supertree containing also the distance information exists, then the method produces a supertree T. This supertree often shows increased resolution over the trees found by methods that utilize only the topology of the input trees. When no strict supertree exists because the input trees are incompatible, an extension of the method still produces a tree with provable properties. (Return to top.)

Apr. 2: Stephen J. Willson, Building supertrees using distances, part II

The talk continues the work in the previous talk regarding supertrees and the BUILD-WITH-DISTANCES method. (Return to top.)

Apr. 9: Roger Maddux, Some problems about coloring the edges of a complete graph

These problems involve coloring the edges a complete graph that has both directed and undirected edges.See a one-page treatment of the problem. (Return to top.)

Apr. 16: Douglas Ray, A greedy algorithm for enhancing cage search

A cubic cage is a regular graph of degree 3 with given girth and a minimum number of vertices. A greedy algorithm that permits extremely sparse descriptions of known cages is presented. I give a number of methods for enhancing algorithm performance. I also give a strategy for looking for better bounds on as yet unknown cages. [This is the public portion of a master's thesis defense.] (Return to top.)

Apr. 23: Alex Burstein, Restricted Dumont Permutations

Dumont permutations of the first kind are those where even letters are followed by a descent and odd letters are followed by an ascent or end the string. Dumont permutations of the second kind are those with all excedences and fixed points in the odd positions and all deficiencies in the even positions. We investigate the structure and enumerate Dumont permutations of both kinds restricted by some 3- and 4- letter permutations, particularly by 4-letter Dumont permutations, together with other permutations. We consider a connection to Chebyshev polynomials, and show that some enumerative results include Catalan numbers or generalized Catalan numbers. [This talk extends work discussed in the Algebra/Combinatorics seminar in December 2003.] (Return to top.)