Discrete Mathematics Group at URI

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

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

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