Discrete Mathematics Seminar
Spring 2019
June 7  P. Morris, Freie Universitaet Berlin  Tilings in randomly perturbed graphs: bridging the gap between HajnalSzemer\'edi and JohanssonKahnVu 
Abstract:
A perfect $K_r$tiling in a graph $G$ is a collection of vertexdisjoint copies of $K_r$ that together cover all the
vertices in $G$. In this paper we consider perfect $K_r$tilings in the setting of randomly perturbed graphs; a model
introduced by Bohman, Frieze and Martin where one starts with a dense graph and then adds $m$ random edges to it.
Specifically, given any fixed $0< \alpha <11/r$ we determine how many random edges one must add to an $n$vertex graph
$G$ of minimum degree $\delta (G) \geq \alpha n$ to ensure that, asymptotically almost surely, the resulting graph contains
a perfect $K_r$tiling. As one increases $\alpha$ we demonstrate that the number of random edges required `jumps' at regular
intervals, and within these intervals our result is bestpossible. This work therefore closes the gap between the seminal work
of Johansson, Kahn and Vu (which resolves the purely random case, i.e., $\alpha =0$) and that of Hajnal and Szemer\'edi
(which demonstrates that for $\alpha \geq 11/r$ the initial graph already houses the desired perfect $K_r$tiling).
This is joint work with Jie Han and Andrew Treglown.
Host: Jie Han 

April 26  E. Fiore, URI  'Spectral Characterizations of Almost Complete Graphs' by M. Camara and W. Haemers 


April 19  A. Clifford, URI  'Graphs with average degree smaller than 30/11 burn slowly' by P. Pralat 


April 12  M. Kowalski, URI  'Upper bounds on sets of orthogonal colorings of graphs' by Serge C. Ballif 
Abstract:
In a recent article, Serge C. Ballif took the notion of orthogonal latin squares and generalized it to other latin structures by considering orthogonal colorings of graphs. In my talk I will define orthogonal colorings and provide many examples. I will also be presenting Ballif's upper bounds of the possible number of mutually orthogonal colorings of a graph and applying them to various latin structures.


March 29  J. Kim, Mathematics Institute, University of Warwick  On the exponents of Turan numbers 
Abstract:
The extremal number $ex(n,F)$ of a graph $F$ is the maximum number of edges in an $n$vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with $ex(n , F) = \Theta(n^r)$.
Erdos and Simonovits conjectured that every rational number in $[1,2]$ is realisable. We show that $2  \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known realisable numbers. This is joint work with Dong Yeap Kang and Hong Liu.
Host: Jie Han 

March 22  M. Barrus, URI  Higher connectivities for realization graphs 
Abstract:
The realization graph of a degree sequence d is the graph whose vertices are the labeled realizations of d (i.e., the graphs having degree sequence d), with two of these ``realizationvertices'' adjacent exactly when the realizations can be transformed into each other by a simple edgeswitching operation. It is well known that the realization graph is connected for any d. After introducing realization graphs with pictures and open questions, we'll see that all but two realization graphs are 2connected, discuss an analogous proof for connectivity 3, comment on the possibility of a 4connected analogue, and conjecture a 5connected version (and beyond).


March 1  J. Guillaume, URI  Closure under Majorization 
Abstract:
Consider the set of partitions of a positive integer $n$ and implement an arrangement or ordering of its members using the following relation: Given two nonnegative integer sequences $d= (d_1, \cdots, d_n)$ and $e = (e_1, \cdots , e_p)$ where $d_i, e_i \geq 1,$ we say that $d$ majorizes $e$, denoted $d \succeq e$, if the terms of $d$ and $e$ add up to a common sum, and the partial sums of $d$ are always greater than or equal to the corresponding partial sums of $e.$ This majorization relation gives rise to a poset or partially ordered set called the dominance order and where the graphic partition(s) are known to form an ideal or downward closed set [Ruch & Gutman, 1979]. Furthermore, Merris showed in 2002 that degree sequences of split graphs form an ``upwardsclosed" set in the dominance order. The same is true for threshold graphs. Coincidentally, these classes of graphs are known to possess some very nice properties. To give context to these examples and better understand how degree sequences of classes of graphs situate themselves in the dominance order, I will define what it means for a collection of graphs ${\mathcal F}$ to be dominance monotone and proceed to characterize the dominance monotone sets ${\mathcal F}$ for ``small'' families ${\mathcal F}$.


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 nvertex 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^{11/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:
VeryLargeScaleIntegration (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 trectangle 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 trectangle 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.  