Discrete Mathematics involves the study of the properties, algorithms and applications of mathematical structures built on discrete objects. Our faculty members in this area are primarily concerned with the theoretical and algorithmic issues pertaining to Graph Theory and Combinatorial Designs.
A graph consists of V (a set of vertices) and E (a set of edges, either ordered or unordered, joining pairs of vertices in V). It is clear that any binary relation may be modeled as a graph; thus, applications of graphs pervade computer science. The interests of our faculty include computational biology, random structures and the structure of electrical circuits, as well as more traditional graph theory such as graph colouring, perfect graphs, hamiltonicity and generalizations of graphs.
A combinatorial design is a collection of sets satisfying some given regularity properties of its subsets. The structures can be as loose as regular graphs or as tight as finite projective geometries. The fundamental problems of design theory are the existence, enumeration and generation of designs with given parameters. Applications of designs are found in statistics (the design of experiments), error-correcting codes, computer architecture and cryptography. Our group’s interests include the development and analysis of deterministic and randomized combinatorial search techniques, algebraic methods for the construction of solutions to combinatorial optimization problems, sub-object and/or automorphism-free systems, systems containing specified small partial systems and design invariants.