Mathematics Department

Basic Notions Seminar

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
  • Nov
    16
  • TBA
    Mark Kidwell
    USNA
    Location: CH320
    Time: 12:00 PM
  • Nov
    09
  • TBA
    Elizabeth McGuffey
    USNA
    Location: CH320
    Time: 12:00 PM
  • Nov
    02
  • TBA
    Marius Ionescu
    USNA
    Location: CH320
    Time: 12:00 PM
  • 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
  • Adventures in p-ary functions
    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->GF(p).
  • Sep
    14
  • What is a flag incidence algebra?
    Max Wakefield
    Naval Academy
    Location: Seminar Room
    Time: 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.
go to Top