Discrete Mathematics Seminar

Spring 2019
February 1 J. Han, URI The number of Gallai colorings
Abstract:    An edge coloring of the complete graph $K_n$ is called a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle in which all three edges have distinct colors. Given a set of $k$ colors and integer $n$, we are interested in the number of Gallai colorings of $K_n$ with colors from the given set. In particular, we show that for $k$ at most exponential in $n$, namely, $k < 2^{n/4300}$, almost all Gallai colorings use at most $2$ colors. Interestingly, this statement fails for $k > 2^{n/2}$.
This is joint work with Josefran O. Bastos and Fabricio S. Benevides (University of Ceara, Brazil).

Fall 2018
December 7 N. Townsend, URI Cops and Robbers with a Fast Robber
Abstract:    In the game of Cops and Robbers, a team of cops and a robber take turns moving on the vertex set of a connected graph. If a cop occupies the same vertex as the robber, then the cops win; if the robber can evade the cops indefinitely, then he wins. We cover the results of a thesis by Abbas Mehrabian, which focuses on the variant where the robber can traverse more than one edge on a single turn. Mehrabian categorizes all graphs on which one cop can win, and provides some lower bounds for the number of cops needed to catch a "fast" robber on varying types of n-vertex graphs.
November 9 M. Schacht, Yale Univesity and Universitaet Hamburg Homomorphism threshold for graphs
Abstract:    The interplay of minimum degree and 'structural properties' of large graphs with a given forbidden subgraph is a central topic in extremal graph theory. For a given graph $F$ we define the homomorphism threshold as the infimum $\alpha$ such that every $n$-vertex $F$-free graph $G$ with minimum degree $>\alpha n$ has a homomorphic image $H$ of bounded size (independent of $n$), which is $F$-free as well. Without the restriction of $H$ being $F$-free we recover the definition of the chromatic threshold, which was determined for every graph $F$ by Allen et al. The homomorphism threshold is less understood and we present recent joint work with O. Ebsen on the homomorphism threshold for odd cycles.
Host: Jie Han
November 2 M. Barrus, URI Connecting induced subgraphs and the adjacency spectrum of a graph
Abstract:    Spectral graph theory considers relationships between properties of graphs and the eigenvalues and eigenvectors of the graphs' adjacency matrices (or other similarly defined matrices). Some well known classes of graphs, such as bipartite graphs, have complete characterizations in terms of adjacency spectra. In this talk we will examine graph classes that, like the bipartite graphs, have both spectral characterizations and forbidden induced subgraph characterizations. After some examples and preliminaries, we will present a recent result of Jiang and Polyanskii on the number of forbidden subgraphs for the class of graphs with bounded spectral radius. We will conclude by discussing graph classes characterized by their adjacency spectra and, independently, by a single forbidden induced subgraph.
October 26 M. Tait, Carnegie Mellon University Using random polynomials in extremal graph theory
Abstract:    For a fixed integer $k$ we consider the problem of how many edges may be in an $n$-vertex graph where no pair of vertices have $t$ internally disjoint paths of length $k$ between them. When $t=2$ this is the notorious even cycle problem. We show that such a graph has at most $c_k t^{1-1/k}n^{1+1/k}$ edges, and we use graphs constructed via random polynomials to show that the dependence on $t$ is correct when $k$ is odd.
October 19 E. Peterson, URI Rectangle Visibility Numbers of Graphs
Abstract:    Very-Large-Scale-Integration (VLSI) in circuitry design is the arrangement of components on the surface of a physical chip and the layout of a wiring network between components. Designing such a system can be loosely modeled in a graph theoretic setting where the components are vertices and the wires are edges. A graph with a t-rectangle visibility representation is one whose vertices can be assigned to at most t rectangles with physical area in the plane such that each edge can be assigned to either a horizontal or vertical uninterrupted channel. We call the rectangle visibility number of a graph the minimum value of t for which G has a t-rectangle visibility representation. In this talk, we will explore rectangle visibility numbers of trees and complete graphs and explore physical layouts of these graphs.
September 29 Discrete Math Day at the University of Rhode Island.

Past semesters:

           2017-2018               2016-2017               2015-2016               2014-2015   
           2013-2014               2012-2013               2011-2012               2010-2011   
           2009-2010               2008-2009               2007-2008               2006-2007   
           2005-2006               2004-2005               2003-2004               2002-2003   

Journals in Discrete Mathematics and related fields