S. Gill Williamson
Faculty-Emeritus, Computer Science and Engineering
Discrete mathematics, algorithmic and algebraic combinatorics, graph theory.
Professor Williamson’s studies have been in algebraic and algorithmic combinatorics . In algebraic combinatorics, he has studied tensor algebras and combinatorial problems related to group theory, noncommuting straightening bases, higher order Capelli identities, and Polya-deBruin theory of enumeration. In algorithmic combinatorics he developed (e.g., in his book Combinatorics for Computer Science) a graph theoretic approach to the design of efficient algorithms. He used this approach to construct optimal (linear time in vertices) algorithms for finding obstructions to planarity (e.g., Kuratowski subgraphs) and to study optimal algorithms for ranking, listing and randomly generating a wide variety of basic finite sets of combinatorial interest. He has studied foundational issues related to graph algorithms. This work includes poset graphs and their incomparability graphs (with J. Remmel) and a class of graph algorithms called lattice-exit problems. In both cases easily stated conjectures arise which have (and require) proofs using statements independent of the ZFC axioms (independence results due to H. Friedman).
Capsule Bio:
Capsule Bio: S. Gill Williamson joined the UCSD faculty in 1965. He was in Mathematics from 1965 to 1991. In 1965 he joined Computer Science and Engineering where he served as department chair from 1991 to 1996. He retired from CSE in 2004 and is now Professor Emeritus, Computer Science and Engineering. He is author of the book Combinatorics for Computer Science, a beginning graduate text in combinatorial algorithms, and the book Top-down Calculus. He is coauthor of three books with E. Bender: Foundations of Combinatorics with Applications, A Short Course in Discrete Mathematics, and Mathematics for Algorithm and Systems Analysis. He received a B.S. in Mathematics from Caltech in 1960, an M.S. in Statistics from Stanford in 1962, and a Ph.D. in Mathematics from the University of California Santa Barbara in 1965.
