# 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.