Graphs & Games @ Dal: Courses

MATH 3300 Introduction to Graph Theory

This course gives introduction to graph theory, with an emphasis on applications and modelling. The course is well suited for students doing a double major in Math and another subject such as Biology or Computer Science. It is also recommended for Science students with a strong interest in Math that want to take a third year Math elective. This course is a good choice for Math students that are considering a specialization in Graph Theory or Combinatorics, and for those that are aiming for a Math Education degree. Topics include:

Paths, cycles and the concept of diameter: are all humans really connected by at most "six degrees of separation"?
Shortest paths: What is the shortest way of routing packets through the Internet?
Connectivity, strong connectivity, connected components: communities in social networks
Connectivity and spanning trees: what is the minimum cost, or maximum reliability network needed to connect a set of servers?
Minimum flow and maximum cut: how scheduling problems can be solved efficiently using graph theory
Graph colouring: assigning radio frequencies in cellular networks
Graph models: how graphs are used to model real-life networks such as ecological networks, the World Wide Web, the Internet, biological networks, and social networks.

MATH 4330/5330 Topics in Graph Theory

This is an advanced course in Graph Theory for 4th year undergraduate or graduate students in Mathematics and Computer Science with a strong interest in graph theory. A limited number of graph-theoretic topics will be treated in detail, and will be used to illustrate general principles in attacking graph-theoretic problems. This course takes a theoretical, proof-based approach, even if the topics can be inspired by applications. Prerequisites are MATH 3300 or CSCI 3115, but please do talk to the instructor if you have a different background that may be sufficient. Topics will generally be chosen to fit the research interests of the instructor. Examples are:

Graph colouring: how to colour the vertices of a graph so that adjacent vertices have different colours, and use a minimum number of colours.
Graph polynomials: there are a number of polynomials that can be associated with a graph. Where can the zeros of such polynomials occur?
Graph products: graphs can be combined to form new graphs. For example, each vertex of one graph could be replaced by a copy of the second graph, and each edge replaced by a complete bipartite graph between the copies. How do various graph parameters of the graph product depend on the graphs from which it was formed?
Graph search: how many cops does it take to catch a robber, if both have the same speed, and can only move along the edges of a graph?

MATH 4340/5340 Discrete Random Structures

This course explores discrete structures, such as graphs, partial orders, or sets, which are formed through a random process. By using randomness, we can discover properties that such sructures are likely to have. Randomness can also be used to model real-life processes, such as Web surfing or making Facebook friends.

MATH 4360/5360 Combinatorial Modelling

This course introduces a common framework for combinatorial structures (graphs, digraphs, hypergraphs, posets, perorders, lattices, finite topologies, simplicial complexes), with an emphasis on how to model these structures with other fields of mathematics, such as linear algebra, commutative algebra, topology, analysis, probability and logic.

MATH 4900/5900 Combinatorial Game Theory

This course looks at 2-player games of strategy, where there are no chance devices and both players have perfect infomration. The surprising mathematical structure underlying these games will be introduced along with the evaluation scheme and its applications to specific games in the classes of hot, all-small and impartial games.

MATH 4xxx/5xxx Combinatorics

A course in Combinatorics is under construction. This course aims to give students a firm basis in combinatorial techniques and structures. The course is expected to be offered in 2012-2013.

RELATED COURSES These courses are often taught by Graphs & Games members, and they fit well with Combinatorics courses.

MATH 3300 Optimization

This course is an introduction to the concepts and applications of linear and non-linear programming. Topics include the simplex method for linear programming, duality and sensitivity analysis, integer programming programming, network flows. Students will learn how to model industrial problems and cast them as linear or integer programs. The topics and techniques will be illustrated through the use of software packages.

MATH 3340 Game Theory

This course will cover the important concepts of classical game theory: game trees, dominance, zero-sum games, saddle points, utility theory, non-zero sum games, Nash equilibrium, non-competitive solutions, Prisoner's dilemma, Chicken, Newcomb's problem. There will be applications to many areas including anthropology, biology, business, economics and philosophy.

MATH 4800 Introduction to Mathematical Research

This class is intended to introduce students to the science and methodology of research in the mathematical sciences. The class will be organized around topics from a wide spectrum of mathematics from which students will be guided to investigage open problems. Conjectures will be formulated and evidence will be developed.