2002 Mt. Baldy Conference on Applied Algebra and Combinatorics: Abstracts
Ron Graham (University of California, San Diego): Guessing Secrets
We will describe a variant of the familiar “20 Questions” problem in which one tries to discover the identity of some unknown "secret" by asking binary questions. In this variation, there is now a set of two (or more) secrets to use in supplying the answers, which in any case must always be truthful. We will discuss a number of algorithms for dealing with this problem, although we are still far from a complete understanding of the situation. Problems of this type have recently arisen in connection with certain Internet traffic routing applications, although it turns out that such problems have in fact occurred in the literature nearly 40 years ago.
Cheryl Praeger (University of Western Australia): Finding and Using the Automorphism Group of a Finite Vertex-Transitive Graph
Finding the full automorphism group of a graph is notoriously difficult, even if the graph is known to be vertex-transitive. However the level of information needed depends on how we wish to apply it and what problems we hope to solve. I shall discuss several families of finite vertex-transitive graphs. The techniques employed to study them range from elementary combinatorial arguments to sophisticated group theory involving finite simple groups.
Fan Chung Graham (University of California, San Diego): Random Graphs and Internet Graphs
Many very large graphs that arise in Internet and telecommunications applications share various properties with random graphs (while some differences remain). We will discuss some recent developments and mention a number of problems and results in random graphs and algorithmic design suggested by the study of these "massive" graphs.
Persi Diaconis (Stanford University): Computational Aspects of Polya Theory
Polya theory is about counting “things” up to symmetry (e.g., unlabeled trees of various flavors). I will review and show how the computer has changed things. Fortunately, there are still things for mathematicians to do.