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, hybrid mode (zoom or Lippitt 205). Seminar archive.

Speaker Michael Barrus, URI
Title Cliques in the realization graph of a degree sequence
Time Friday March 25, 2022, 1pm, zoom
Abstract Given a degree sequence $d$ of a finite graph, there are usually many different realizations of the sequence by labeled graphs. The realization graph of $d$ is the graph whose vertices are these realizations, where edges join vertices corresponding to realizations that can be changed into each other via single editing operation on an edge set. The realization graph is known to be connected for all $d$, and it is conjectured that it always has a Hamilton path or cycle. After a quick introduction to the realization graph, we present a necessary and sufficient condition for cliques of any fixed size to appear in the realization graph. We also determine the degree sequences $d$ whose realization graph is the complete graph $K_n$ for all $n$. This is joint work with Nathan Haronian (Brown University).

News


Faculty and their research
     Michael Barrus, graph theory
     Nancy Eaton, graph theory
     Barbara Kaskosz, analysis and its applications to discrete mathematics
     William Kinnersley, graph theory and combinatorial games
     Lubos Thoma, extremal and probabilistic combinatorics

Doctoral students
     Emily Barranca
     Erika Fiore
     John Jones
     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
MIT Combinatorics seminar Brown Discrete Mathematics seminar / applied seminars
MIT Probability seminar Yale Combinatorics and probability seminar
ICERM CMSA