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 co-TT graphs) admit intersection models that are remarkably similar to interval graphs.
Due to how similar co-TT graphs are to interval graphs, one would expect that the co-TT class would at this point also be well-understood. Surprisingly, the complexity for recognition of the co-TT class is currently O(n4) and no forbidden induced subgraph characterization is known. We explore the structure of co-TT graphs and exploit it to give an O(n2) recognition algorithm for the co-TT class. We also investigate some generalizations and restrictions of the co-TT 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 n-cells, does not depend on the division. The number ∑(−1)nαn is referred to as the Euler characteristic χ(X). The Gauss-Bonnet 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 3-space is independent of the embedding. Of central importance in combinatorial topology is a combinatorial version of the Gauss-Bonnet theorem. In my talk I will state and prove this theorem and will survey applications to group theory and 2-dimensional 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:
|
|
