Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2023

April 21 R. Griffin, URI On gaps in the gaussian primes

It is known that one cannot walk to infinity on the real line using only primes and steps of bounded length. We will survey what is known on the same problem for Gaussian primes in $\mathbb{Z}[i]$. The later problem is presently unresolved. The MS presentation is based on papers by M. Das (Walking through the Gaussian Primes) and by E. Gethner, S. Wagon, B. Wick (A Stroll through the Gaussian Primes).

April 14 M. Barrus, URI Distinguishing chromatic numbers of hamiltonian circulant graphs

The distinguishing chromatic number of a graph $G$ is the minimum number of colors needed to properly color the vertices so that no nontrivial symmetry of $G$ preserves the coloring. Providing many examples of the twists and turns symmetries introduce, we determine the distinguishing chromatic number of circulant graphs with connection set $\{ \pm 1, \pm k\}$. This is joint work with Jean Guillaume (Sacred Heart University) and Benjamin Lantz (Wheaton College).

March 31 E. Barranca, URI Characterizing some graphs which are recognizable by spectrum

A graph is said to be determined by its spectrum (DS) if its adjacency spectrum is not shared by any nonisomorphic graphs. In this presentation we explore an extension to the question of determining which graphs are DS. We say a graph $G$ is recognizable by spectrum (RS) if any graph's spectrum determines if it contains $G$ as an induced subgraph. We will present examples of graphs which are RS and, in our attempt to characterize small RS graphs, we will share results focusing on trees and graphs with special cycles and cliques.

Fall 2022

December 2 D. Johnston, Trinity College, Hartford CT Rainbow Turan Numbers and Rainbow Saturation

Abstract: Extremal graph theory asks questions of the form: What is the maximum or minimum size of a graph satisfying certain conditions? For example, Turan investigated the maximum number of edges in a graph on $n$ vertices that avoids a given subgraph $F$, denoted by $ex(n; F)$. Keevash, Mubayi, Sudakov and Verstraete extended this idea to graphs with proper edge-colorings: colorings of the edges of a graph so that adjacent edges have different colors. For a given subgraph $F$, they studied the maximum number of edges in a properly edge-colored graph on $n$ vertices that does not contain a rainbow copy of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^*(n; F)$, is the rainbow Turan number of $F$. In this talk, we examine rainbow Turan numbers and answer the question, In what way does instead looking at the minimum number of edges in the context above make sense? by introducing the rainbow saturation number of $F$. Host Mike Barrus.



April 21	R. Griffin, URI	On gaps in the gaussian primes
		It is known that one cannot walk to infinity on the real line using only primes and steps of bounded length. We will survey what is known on the same problem for Gaussian primes in $\mathbb{Z}[i]$. The later problem is presently unresolved. The MS presentation is based on papers by M. Das (Walking through the Gaussian Primes) and by E. Gethner, S. Wagon, B. Wick (A Stroll through the Gaussian Primes).
April 14	M. Barrus, URI	Distinguishing chromatic numbers of hamiltonian circulant graphs
		The distinguishing chromatic number of a graph $G$ is the minimum number of colors needed to properly color the vertices so that no nontrivial symmetry of $G$ preserves the coloring. Providing many examples of the twists and turns symmetries introduce, we determine the distinguishing chromatic number of circulant graphs with connection set $\{ \pm 1, \pm k\}$. This is joint work with Jean Guillaume (Sacred Heart University) and Benjamin Lantz (Wheaton College).
March 31	E. Barranca, URI	Characterizing some graphs which are recognizable by spectrum
		A graph is said to be determined by its spectrum (DS) if its adjacency spectrum is not shared by any nonisomorphic graphs. In this presentation we explore an extension to the question of determining which graphs are DS. We say a graph $G$ is recognizable by spectrum (RS) if any graph's spectrum determines if it contains $G$ as an induced subgraph. We will present examples of graphs which are RS and, in our attempt to characterize small RS graphs, we will share results focusing on trees and graphs with special cycles and cliques.

December 2	D. Johnston, Trinity College, Hartford CT	Rainbow Turan Numbers and Rainbow Saturation
		Abstract: Extremal graph theory asks questions of the form: What is the maximum or minimum size of a graph satisfying certain conditions? For example, Turan investigated the maximum number of edges in a graph on $n$ vertices that avoids a given subgraph $F$, denoted by $ex(n; F)$. Keevash, Mubayi, Sudakov and Verstraete extended this idea to graphs with proper edge-colorings: colorings of the edges of a graph so that adjacent edges have different colors. For a given subgraph $F$, they studied the maximum number of edges in a properly edge-colored graph on $n$ vertices that does not contain a rainbow copy of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^(n; F)$, is the rainbow Turan number* of $F$. In this talk, we examine rainbow Turan numbers and answer the question, In what way does instead looking at the minimum number of edges in the context above make sense? by introducing the rainbow saturation number of $F$. Host Mike Barrus.