Discrete Mathematics Seminar

Spring 2015
April 17 J. Jones, URI Report on Recontamination does not help to search a graph by A. LaPaugh.
April 10 M. Krul, Emmanuel College Polynomial ideals and their applications to graph and hypergraph theory.
April 03 A. Armstrong, URI Planar Graphs are (4,1) Choosable. A theorem by Cushing and Kierstead.
March 27 L. Hamel, URI Automatic Theorem Proving: A Very Brief Introduction
Abstract:    Automatic theorem proving is interesting because it shifts the burden of proof from the user to the machine. In this talk we briefly survey the differences between fully automatic theorem provers and proof assistants. We show that the latter seems more promising as a tool because of deep theoretical limitations of the former. We then turn our attention of the field of formal programming language semantics and show that here Prolog viewed as a proof assistant works very well and has a much more gradual learning curve than some of the other well known proof assistants.
March 20 spring break
Feb 27, Mar 6 job interviews
February 20 M. Barrus, URI Uniqueness and minimal obstructions for tree-depth
February 13 L. Thoma, URI The regularity lemma: a proof by A. Schrijver - III
February 6 L. Thoma, URI The regularity lemma: a proof by A. Schrijver - II
January 30 L. Thoma, URI The regularity lemma: a proof by A. Schrijver - I

Fall 2014
October 31 N. Finizio, URI ZCPS-starters: necessary and sufficient conditions for the existence of ZCPS-whist designs
October 15 D. Cranston Painting squares of graphs with $\Delta^2-1$ colors
Virginia Commonwealth University Abstract:    Brooks' Theorem states that if $G$ is a connected graph with maximum degree $\Delta$ at least 3, then $G$ can be colored with $\Delta$ colors. This result has been generalized to list-coloring and more general contexts. The square $G^2$ of a graph $G$ is formed from $G$ by adding an edge between each pair of vertices at distance two. When $G$ has maximum degree $\Delta$, it is easy to show that $G^2$ has maximum degree at most $\Delta^2$; so Brooks' Theorem implies that $G^2$ can be colored with $\Delta^2$ colors. Cranston and Kim conjectured that we can improve this upper bound by at least 1. Specifically, they conjectured that $\chi_{\ell}(G^2) \le \Delta^2-1$ unless $G$ is a Moore graph (here $\chi_{\ell}$ denotes the list chromatic number). We prove their conjecture and survey some harder conjectures about coloring squares of graphs. This is joint work with Landon Rabern.
October 3 L. Thoma, URI Semigroups, quasi-orders, and some applications
September 26 M. Barrus, URI The polytope of fractional realizations of degree sequences
Abstract:    Fractional graph theory takes familiar graph-theoretic parameters and structures and studies what happens when the associated numbers are no longer required to be integers. In this talk, I will introduce a convex polytope that arises when we study "fractional" realizations of the degree sequence of a simple graph. After observing how closely the vertices of the polytope mimic traditional degree sequence realizations in general, we will see that for a certain class of graphs (the decisive graphs) the correspondence is exact. We describe the structure of the decisive graphs and their degree sequences and show that many properties of threshold graphs and split graphs can be generalized to properties that characterize all decisive graphs.
September 19 W. Kinnersley, URI Degree ramsey and online degree ramsey numbers
September 12 A. Kodess, URI Properties of some algebraically defined digraphs