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