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. | |