Mathematics Department

# Basic Notions Seminars

## Fall Semester 2015

All talks are from 12:00-1:00 p.m. in the Seminar room, unless otherwise specified.

• Dec
07
• Graph theoretic change detection
Matthew Halk
USNA
Location: CH320
Time: 12:00 PM

#### View Abstract

TBA
• Nov
16
• TBA
Mark Kidwell
USNA
Location: CH320
Time: 12:00 PM

#### View Abstract

TBA
• Nov
09
• TBA
Elizabeth McGuffey
USNA
Location: CH320
Time: 12:00 PM

#### View Abstract

TBA
• Nov
02
• TBA
Marius Ionescu
USNA
Location: CH320
Time: 12:00 PM

#### View Abstract

TBA
• Oct
19
• NP-Completeness of 3-colorability
Chris Griffin
USNA
Location: CH320
Time: 12:00 PM

#### View Abstract

A graph is a mathematical object (invented by Euler) that consists of points (vertices) and lines (edges) connecting them. Graphs are fundamental structures in discrete mathematics and find uses in GPS, social networks and the biggest graph of all, the Internet. Imagine choosing k distinct colors (red, blue, green etc.) and trying to color an arbitrary graph so that no two vertices joined by an edge share the same color. We call this a proper coloring. How hard could it be to find a proper coloring of a graph? It turns out, potentially very hard. In 1972, Karp showed (among other things) that deciding whether a graph could be properly colored using just 3 colors was NP-complete. This proof is among the most visual in mathematics, relying on a series of "gadgets" to encode expressions in mathematical logic in terms of graph colorings. In this talk, we will survey the basic notions needed to understand the proof that the question: "Is a graph properly 3-colorable?" is NP-complete and see this beautifully visual proof first hand.
• Oct
05
• TBA
David Seal
Location: CH320
Time: 12:00 PM
• Sep
21
David Joyner
USNA
Location: CH320
Time: 12:00 PM

#### View Abstract

A survey of recent and not-so-recent results on the combinatorics of functions f:GF(p)^m-&gt;GF(p).
• Sep
14
• What is a flag incidence algebra?
Max Wakefield