Discrete Mathematics Group at URI


The faculty of our group is interested in a wide range of areas in discrete mathematics both pure and applied: graph theory, network theory, extremal and probabilistic methods, analytic methods, finite model theory, combinatorial games, combinatorial optimization, bioinformatics applications.

Seminar  Our seminar is held Fridays 1-2pm in Lippitt 205. Seminar archive.

Speaker Mathias Schacht, Yale University and Universitaet Hamburg
Title Homomorphism threshold for graphs
Time Friday November 9, 2018, 1-2pm, Lippitt 205
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

News


Faculty and their research
     Michael Barrus, graph theory
     Nancy Eaton, Associate Dean at the College of Arts and Sciences, graph theory
     Jie Han, extremal and probabilistic combinatorics
     Barbara Kaskosz, analysis and its applications to discrete mathematics
     William Kinnersley, graph theory and combinatorial games
     Lubos Thoma, extremal and probabilistic combinatorics

Doctoral students
     Jean Guillaume
     John Jones
     Benjamin Lantz
     Eric Peterson
     Nikolas Townsend

Graduate courses   MTH547 Combinatorics, MTH548 Graph Theory, MTH515/516 Algebra, MTH550 Probability and Stochastic Processes, MTH581 Optimization Methods, MTH656 Probability on Discrete Structures, CSC541 Advanced Topics in Algorithms, CSC542 Mathematical Analysis of Algorithms, CSC544 Theory of Computation, Special topics courses in Extremal Graph Theory, Ramsey Theory, Algebraic Combinatorics.

Discrete mathematics nearby