Basic Notions Seminars
Fall Semester 2015
All talks are from 12:001:00 p.m. in the Seminar room, unless otherwise specified.

Dec07

Nov16

Nov09

Nov02

Oct19

NPCompleteness of 3colorabilityChris GriffinUSNALocation: CH320Time: 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 NPcomplete. 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 3colorable?" is NPcomplete and see this beautifully visual proof first hand.

Oct05

TBADavid SealLocation: CH320Time: 12:00 PM

Sep21

Adventures in pary functionsDavid JoynerUSNALocation: CH320Time: 12:00 PM
View Abstract
A survey of recent and notsorecent results on the combinatorics of functions f:GF(p)^m>GF(p).

Sep14

What is a flag incidence algebra?Max WakefieldNaval AcademyLocation: Seminar RoomTime: 12:00 PM
View Abstract
A classical incidence algebra contains many important invariants throughout mathematics. In this lecture we will examine applications in number theory (Euler's phi function), geometry (Euler characteristic), and graph theory (chromatic polynomial). Then we will describe a possible generalization to higher dimensions which we call a flag incidence algebra.