Discrete Mathematics Seminar


Fall 2018
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