2004-2005 ARCHIVE
Focus of seminar:
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.)
Post-Mortem on the Extremal Combinatorics
session of the Central Sectional Meeting of the AMS
Maria Axenovich, Jess Campbell, Ryan Martin, Amy Wangsness,
ISU Math Department
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.)
