MathematicsSeminar 
Rocky Mountain Algebraic Combinatorics Seminar
On Threshold Tolerance Graphs and their Complements
Nathan Lindzey
Colorado State University
A graph is threshold tolerance if it is possible to associate a weight and a tolerance to each vertex such that two vertices are adjacent exactly when the sum of their weights exceeds either of their tolerances. Monma, Reed, and Trotter (1988) show that the complements of threshold tolerance graphs (the coTT graphs) admit intersection models that are remarkably similar to interval graphs.
Due to how similar coTT graphs are to interval graphs, one would expect that the coTT class would at this point also be wellunderstood. Surprisingly, the complexity for recognition of the coTT class is currently O(n^{4}) and no forbidden induced subgraph characterization is known. We explore the structure of coTT graphs and exploit it to give an O(n^{2}) recognition algorithm for the coTT class. We also investigate some generalizations and restrictions of the coTT class to gain insight into a minimal forbidden induced subgraph characterization for the class. The talk is based on joint work with Ross McConnell.
Combinatorial Topology in Dimension 2
Jens Harlander
Boise State University
Euler's formula, published in 1758, states that if Γ is a planar connected graph then α_{0}−α_{1}+α_{2}=2, where α_{0} is the number of vertices, α_{1} is the number of edges, and α_{2} is the number of regions. At the beginning of the 20th century Poincare observed (but did not prove) that Euler's formula holds true in a much more general setting. If a space X is divided up into finitely many cells, then the alternating sum ∑(−1)^{n}α_{n}, where α_{n} is the number of ncells, does not depend on the division. The number ∑(−1)^{n}α_{n} is referred to as the Euler characteristic χ(X). The GaussBonnet theorem (known to Gauss but proved by Bonnet in 1848) provides a differential geometric version of Euler's formula. It states that the total curvature of a surface M is 2πχ(M). Intuitively this says that the total curvature of a surface embedded in 3space is independent of the embedding. Of central importance in combinatorial topology is a combinatorial version of the GaussBonnet theorem. In my talk I will state and prove this theorem and will survey applications to group theory and 2dimensional topology.
Weber 223
4–6 pm
Friday, March 7, 2014
(Refreshments in Weber 117, 3:30–4 pm)
Colorado State University
This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly. Anyone interested is welcome to join us at a local restaurant for dinner after the talks.
PDF version
Previous Seminars:

