Basic Notions Seminars
Fall Semester 2015
All talks are from 12:00-1:00 p.m. in the Seminar room, unless otherwise specified.
-
Dec07
-
Nov16
-
Nov09
-
Nov02
-
Oct19
-
NP-Completeness of 3-colorabilityChris GriffinUSNATime: 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.
-
Oct05
-
TBADavid SealTime: 12:00 PM
-
Sep21
-
Adventures in p-ary functionsDavid JoynerUSNATime: 12:00 PM
View Abstract
A survey of recent and not-so-recent results on the combinatorics of functions f:GF(p)^m->GF(p).
-
Sep14
-
What is a flag incidence algebra?Max WakefieldNaval AcademyTime: 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.
