Main Page: CLICK HERE
| Spring 2005 Schedule | |||
|---|---|---|---|
| Date | Speaker | Title (click on title to see abstract) | |
| Jan. | 13 | Amy Wangsness | Report on graph theory from AMS Atlanta meeting |
| 18 | Michael Doob, University of Manitoba | Ramanujan Graphs | |
| 20 | NO SEMINAR (met Tuesday instead) | ||
| 25 | Felix Lazebnik, University of Delaware | On Graphs Defined by Some Systems of Equations (Colloqium, 4 PM Tuesday) | |
| 27 | Maria Axenovich | On properties of transversals in vertex-partitions of graphs | |
| Feb. | 3 | Alexander Burstein | Patience sorting, Young tableaux and shadow diagram duality |
| 10 | Ryan Martin | Identification codes and superimposed codes | |
| 17 | Ryan Martin | Identification codes and superimposed codes | |
| 24 | Jess Campbell | Enumeration and Symmetry of Edit Metric Spaces, 408 Carver | |
| Mar. | 1 | Sriram Pemmaraju, University of Iowa | Approximation Algorithms for Max-Coloring (Colloqium, 4 PM Tuesday) |
| 3 | NO SEMINAR (Tuesday colloquium instead) | ||
| 10 | Tim Hardy, William Penn University | Independence in Boolean matrices and sign pattern matrices | |
| 24 | Leslie Hogben | A new graph parameter for minimum rank | |
| 31 | Leslie Hogben | A new graph parameter for minimum rank | |
| Apr. | 7 | Amy Wangsness | |
| 14 | Y. T. Poon | Young Tableaux and some results in matrix theory | |
| 21 | Joohyung Kim | Characterization of some non-isomorphic co-spectral distance regular graphs (DRGs) | |
| 28 | Y. T. Poon | Young Tableaux and some results in matrix theory | |
| Fall 2004 Schedule | |||
|---|---|---|---|
| Date | Speaker | Title (click on title to see abstract) | |
| Aug. | 27 | Ryan Martin | Online Intersecting Hypergraphs II |
| Sep. | 3 | No Seminar | Enjoy your Labor Day weekend! |
| 10 | No Seminar | ||
| 17 | No Seminar | ||
| 24 | Maria Axenovich | On properties of small cycles in the hypercube | |
| Oct. | 1 | Richard Kramer | Avoiding monochromatic triangles |
| 8 | Richard Kramer | Avoiding monochromatic triangles, part II | |
| 15 | Ryan Martin | Vertex identification codes in graphs | |
| 22 | No Seminar | Many participants will be at the AMS Sectional Meeting | |
| 29 | Maria Axenovich, Jess Campbell, Ryan Martin, Amy Wangsness | Post-Mortem on the Extremal Combinatorics session of the Central Sectional Meeting of the AMS | |
| Nov. | 5 | Alex Burstein | Patience sorting and generalized patterns |
| 12 | Leslie Hogben | Spectral Graph Theory | |
| 19 | No Seminar | Get a head start on Thanksgiving! | |
| Dec. | 3 | Douglas Ray | Cayley Graphs |
This seminar is intended to include topics in discrete mathematics (combinatorics and graph theory) and the theory of computation. In particular, we will see extremal graph theory, probabilistic methods, algebraic methods, enumerative combinatorics, association schemes, design theory, algorithms, optimization, complexity theory and other related topics. Students are encouraged to attend and give talks. We are interested in disseminating techniques across these interrelated disciplines. New research is always welcome, but talks on well-established techniques are encouraged.
Online Intersecting Hypergraphs
II
Ryan Martin, ISU Math Department
This talk unveils some new results on the process of selecting hyperedges one-by-one so that the resulting hypergraph is a maximal intersecting hypergraph. Let n and r be fixed. We start with a set of n vertices and select subsets of size r uniformly at random so that what results has all pairs of these subsets with a nonempty intersection. At some point in this process, we run out of eligible subsets. We want to know the point at which this occurs. That is, we want to know how many edges this process will produce.
Recently, the speaker, along with some collaborators, was able to determine that, if r has the property that ω(n1/3)=r=o(n5/12), then, given the outcome of a single random variable, we are able to determine not only the size of the final family, but also its precise structure.
This significantly improves a result presented in a talk last semester, which gave a precise result for r=o(n1/3). (Return to top.)
On properties of small cycles in the
hypercube
Maria Axenovich, ISU Math Department
In this talk we discuss the properties of short cycles in the hypercube. An old open question of Erdõs is to determine the size of the densest subgraph of a hypercube without cycles of length 4. In general, the largest densities of C-free subgraphs of a hypercube are not known for any even cycle. Here we present some new results in this area. (Return to top.)
Avoiding monochromatic triangles
Richard Kramer, ISU Math Department
This talk is on Ramsey theory. (Return to top.)
Avoiding monochromatic triangles, part II
Richard Kramer, ISU Math Department
More on Ramsey theory. (Return to top.)
Vertex identification codes in graphs
Ryan Martin, ISU Math Department
Within the last five years, a different kind of code has emerged in graphs. The vertex identification code is a way of distinguishing nodes in a network to determine which of them has failed. In this talk, we will discuss the origins of the topic and some known results, particularly the results and open questions on hypercubes. Furthermore, we will introduce a probabilistic tool called Suen's inequality which will aid in determining the size of the smallest vertex identification code in a random graph. (Return to top.)
We will report on some selected talks from the above-mentioned conference. The speaker's list includes Penny Haxell, Jozef Skokan, Alexandr Kostochka, Oleg Pikhurko, Jacques Verstraete, André Kézdy, Tom Bohman, Douglas West, Jozsef Balogh, Gerrold Griggs, Tao Jiang, Laszlo Szekely, G.O.H. Katona and Maria Axenovich. (Return to top.)
Patience sorting and generalized patterns
Alex Burstein, ISU Math Department
Abstract TBA. (Return to top.)
Spectral Graph Theory
Leslie Hogben, ISU Math Department
Spectral graph theory began as the study of the spectra of specific matrices defined from the graph, including the adjacency matrix, Laplacian matrix, etc. Over the last fifty years, a large number of results have been obtained describing the spectra of these specific matrices, and extracting information about the graph from the spectrum.
More recently, generalized Laplacians, a whole family of matrices associated with a given graph, have been studied. Colin de Verdiere and others have obtained impressive results characterizing graph properties such as planarity in terms of eigenvalues of generalized Laplacians.
This talk will survey both older and newer results in spectral graph theory. (Return to top.)
Cayley Graphs
Douglas Ray, ISU Math Department
Cayley graphs provide one of the most interesting links between graph theory and algebra. In this talk, connections between Cayley graphs and the structure of their underlying groups and generating sets are presented. The talk includes information on transitivity, cages, and automorphisms as related to Cayley graphs. (Return to top.)
Leslie Hogben's Home Page
Ryan Martin's Home Page
