#### Degree Type

Dissertation

#### Date of Award

2010

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### First Advisor

Maria Axenovich

#### Abstract

Coloring problems concern partitions of structures. The classic problem of partitioning the set of integers into a finite number of pieces so that no one piece has an arithmetic progression of a fixed length was solved in 1927. Van der Waerden's Theorem shows that it is impossible to do so. The theorem states that if the set of positive integers is partitioned into finitely many pieces, then at least one of the pieces contains arbitrarily long arithmetic progressions.

Extremal problems focus on finding the largest (or smallest) structures which exhibit a certain property. For instance, we may wish to find a graph with the most number of edges which does not contain a certain fixed subgraph. The famous theorem of Turan from 1941 is the seminal result in the field of extremal graph theory. The theorem gives the most number of edges in an n-vertex graph which does not contain an r-vertex complete subgraph.

Here, we focus on coloring and extremal problems concerning graphs, the integer grid, and the Boolean lattice.

#### Copyright Owner

Jacob Manske

#### Copyright Date

2010

#### Language

en

#### Date Available

2012-04-30

#### File Format

application/pdf

#### File Size

109 pages

#### Recommended Citation

Manske, Jacob, "Coloring and extremal problems in combinatorics" (2010). *Graduate Theses and Dissertations*. 11457.

https://lib.dr.iastate.edu/etd/11457