Skip to main content

Mathematics Department Directed Reading Program

Number Theory and Combinatorics

This page contains a list of ideas for DRP projects, but is by no means exhaustive.

Topic: Szemeredi’s Regularity Lemma and Applications.
Suggested Text: Graph Theory, written by Reinhard Diestel, Graduate Texts in Mathematics 173
Suggested Background: MATH 4710 Graph Theory
Description:  In the course of the proof of a major result on the Ramsey properties of arithmetic progressions, Szemeredi developed a graph theoretical tool whose fundamental importance has been realized more and more in recent years. Roughly speaking, the lemma says that all graph can be approximated by random graph in the following sense: every graph can be partitioned, into a bounded equal parts, so that most of its edges run between different parts and the edges between any two parts are distributed fairly uniformly–just as we would expect it if they had been generated at random.

Topic: Linear Algebra in Graph Theory
Suggested Text: Algebraic Graph Theory, Norman Biggs
Suggested Background: MATH 2600 Linear Algebra
Description: In the study of algebraic graph theory, the aim is to translate properties of graphs into algebraic properties and then, using the results and methods of algebra, to deduce theorems about graphs. We first introduce the adjacency matrix of graph, which completely determines the graph, and its spectral properties are shown to be related to properties of the graph. Another matrix which completely describes a graph is the incidence matrix of the graph. This matrix represents a linear mapping which determines the homology of the graph.

Topic: Introduction to Random Graphs and Ramsey Theory
Suggested Text: Graph theory and Additive Combinatorics, Yufei Zhao; Random Graphs, Bela Bollobas
Suggested Background: MATH 3640 Probability
Description: The theory of random graphs was founded by Erdos and Renyi had discovered that probabilistic methods were often used in tackling extremal problems in graph theory. Although Erdos did not construct such graphs explicitly but showed that most graphs in a certain class could be altered slightly to give the required examples.