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 |