ISU
DISCRETE
MATHEMATICS
SEMINAR
2007-2008
Time:
Tuesdays 1:10 PM Place:
294 Carver
The Discrete Mathematics Seminar at Iowa State University is an eclectic mix of topics, including graph theory, combinatorics, linear algebra and abstract algebra. Presentations vary with the speaker and include the speaker's research, related research by others, and expository talks. Many of the expository talks (typically labeled as "Introduction to") are suitable for interested graduate students and faculty who are not specialists in the area.
For questions or to volunteer to speak in the seminar, please contact Jason Grout or Ryan Martin
|
Date |
Name |
Title |
Abstract |
|
Jan 15 |
Organizational Meeting |
||
|
Jan 22 |
Luz De Alba |
Matrix Completion Problems |
|
|
Jan 29 |
Luz De Alba |
The Q-matrix Completion Problems |
|
|
Feb 5 |
Maria Axenovich |
On transversals of longest paths in graphs. |
It is an easy fact that any two longest paths in a connected graph share a vertex. It is more difficult to prove that there are graphs in which several (at least 7) longest paths do not share a common vertex. The following question remains open now for several decades. Is it true that any three longest paths in a connected graph share a vertex? We shall discuss several results related to this question. |
|
Feb 12 |
Jack Lutz |
Combinatorial Aspects of Nanoscale Self-Assembly |
DNA tile self-assembly, pioneered by Seeman in the 1980s, is a promising approach to engineering structures that autonomously assemble themselves from molecular components. These structures, which may be complex and aperiodic, can be programmed, in the sense that they are determined by a designer's selection of the finite set of molecular component (DNA tile) types from which the structures self- assemble. The Tile Assembly Model, introduced by Winfree in the late 1990s, is a mathematical model of DNA tile self-assembly. Winfree showed that discrete Sierpinski triangles can self- assemble in the Tile Assembly Model, and a striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic- force microscopy, was achieved by Rothemund, Papadakis, and Winfree in 2004. Winfree also proved that any computer program (Turing machine) can be translated into a finite set of tile types whose self-assembly executes that program. The collection of structures that can be programmed to self-assemble is thus very rich. In this talk I will survey these developments, along with some recent work in which Jim Lathrop, Matt Patitz, Scott Summers, and I have explored the theoretical power and limitations of tile self-assembly. I will also discuss the need for new combinatorial arguments to further this exploration. |
|
Feb 19 |
Ryan Martin |
The Vertex Ramsey Problem. |
|
|
Feb 26 |
Jason Grout |
|
|
|
Mar 4 |
Jake Manske |
Monochromatic subsets of the integer grid |
For an integer n, let [n] denote the integer set {0, 1, ..., n-1}. For any subset V of Z x Z, let Hom(V) = {cV + b : c a positive integer, b an element of Z x Z}. For any positive integer k, let Rk(V) denote the least integer N such that for any n > N and for any k-coloring of [N] x [N], there is a monochromatic subset U from Hom(V). The argument of Gallai ensures that Rk(V) is finite. We investigate bounds on Rk(V) when V is a three or four-point configuration in general position. |
|
Mar 11 |
No seminar in favor of the colloquium by Hemanshu Kaul on |
See the Colloquium schedule for Hemanshu's title and abstract. |
|
|
Mar 18 |
Spring Break; No seminar. |
||
|
Mar 25 |
|
|
|
|
Apr 1 |
Leslie Hogben |
Minimum Rank of Not Necessarily Symmetric Matrix Patterns |
|
|
Apr 8 |
Rana Mikkelson and Kaela Rasmussen |
Universally optimal matrices and field independence of the minimum rank of a graph |
|
|
Apr 15 |
Tracy McKay, Jason Smith |
Software for computation of Minimum Rank |
|
|
Apr 22 |
Laura DeLoss, Geoff Tims |
The Graph Complement Conjecture for Minimum Rank |
|
|
Apr 29 |
Olga Pryporova |
Diagonal and D-convergence of matrices |
|
Upcoming Conferences:
AMS Central Section Meeting (#1038), Apr. 4-6, 2008, Indiana University, Bloomington, IN.
4th annual Graduate Student Combinatorics Conference (GSCC) is April 12-13, 2008 at the University of California, Davis.
Confirmed Invited Speakers: Ron Graham, U.C. San Diego; Arun Ram, U. of Wisconsin
Mathematical Abundance: Designs, Graphs and Number Theory -- a conference honoring the 72nd birthday of Charles Vanden Eynden, April 18-19, 2008, Illinois State University. (There may be student funding available.)
Confirmed Invited Speakers: George Andrews, Penn State; Bruce Berndt, U. of Illinois; Richard Brualdi, U. of Wisconsin; Alex Rosa, Slovak Academy of Sciences
Fall 07 Seminars
Time: Tuesdays 2:10 PM Place: 074 Carver
|
Date |
Name |
Title |
||
|---|---|---|---|---|
|
Aug. 21 |
Welcome and organizational meeting |
|||
|
Aug. 28 |
Jason Grout |
The minimum rank problem over finite fields: |
||
|
Sept. 4 |
||||
|
Sept. 11 |
Alex Roitershtein |
Random strategies for the Robin Hood game |
||
|
Sept. 18 |
Leslie Hogben |
Minimum rank of nonsymmetric matrices described by a digraph |
||
|
Sept. 25 |
||||
|
Th Sept. 27, 3:40pm, |
F.R. (Buck) McMorris, |
Majority-rule
consensus: from preferences |
||
|
Oct. 2 |
Ryan Martin |
Edit distance in graphs: Colored regularity graphs |
||
|
T Oct. 2: 4:10pm,
|
Leif Jorgensen, |
|||
|
Oct. 9 |
Colloquium replaces seminar |
|||
|
T Oct. 9: 4:10pm,
|
Chris Godsil, |
|||
|
Th Oct. 11: 3:30pm,
|
Daniel Gusfield, |
ReCombinatorics: Combinatorial Algorithms for Studying The History of Recombination in Populations |
||
|
Oct. 16 |
Chad Brewbaker |
An Introduction to Computational Genetics for the Graph Theorist |
||
|
Oct. 23 |
Olga Pryporova |
Qualitative Convergence of Matrices |
||
|
Oct. 30 |
Leslie Hogben |
Teaching Linear Algebra: Technology and Resources |
||
|
Nov. 6 |
Seminar replaced by First Year Seminar on Wednesday 4:10pm |
|||
|
W Nov 7: 4:10pm, |
Leslie Hogben |
Minimum Rank Problems and the Early Graduate Research seminar for Spring 08 |
||
|
Nov. 13 |
Seminar replaced by First Year Seminar on Wednesday 4:10pm |
|||
|
W Nov 14: 4:10pm, |
Ryan Martin |
The edit distance in graphs |
||
|
Nov. 20 |
VACATION |
|||
|
Nov. 27 |
Rana Mikkelson |
Minimum rank of graphs with loops |
||
|
Dec. 4 |
Ryan Martin |
|||
Oct. 9: Chris Godsil: Association schemes and type-II matrices
Type-II
matrices are a class of matrices that were used by Vaughan Jones to
construct interesting new invariants of knots and links, known as
spin models. They are closely related to a number of combinatorial
objects, and in particular to association schemes. I this talk I will
develop this connection, and discuss the open problems that result.
Oct. 16: Chad Brewbaker: An Introduction to Computational Genetics for the Graph Theorist
We will
introduce the basic algorithms and biology needed for performing
genome shotgun assembly . Also, we will review some basic properties
of the scale free and sparse near-planar graphs that arise.
Due to the size of these data sets we are only able to recognize and exploit properties of the graph that can be computed in linear or O(E log(E)) time and space where E is the number of edges. Also, since the data sets are so large we must distribute the computations over many computers. We will discuss open challenges related to finding interesting properties of these graphs that can be computed in near-linear time, space, and communication.
Dec. 4: Ryan Martin: Forbidden subgraphs of Unit Disk Graphs
So-called unit disk graphs (UDGs) are graphs in which adjacency is determined by proximity. A finite number of vertices are put in the plane and they are adjacent if and only if they are of distance at most 1 from each other.
Computer scientists study UDGs because of their applications to wireless networks, although very little is known about the structure of UDGs. I will present some very new results on UDGs as a result of joint work with Hemanshu Kaul of the Illinois Institute of Technology. He will be visiting ISU in March.
The proof techniques involve basic geometry and the answer to the question "Why can't I draw a Venn diagram with 4 circles?"
Upcoming Conferences:
AMS Central Section Meeting (#1030), Oct. 5-6, 2007, DePaul University, Chicago, IL. (There will be a van from ISU.) [Registration/Housing]
Special sessions: Algebraic Combinatorics: Association Schemes and Related Topics, Extremal and Probabilistic Combinatorics, Graph Theory, Algorithmic Probability and Combinatorics
Archives: S07,
F06,
S06,
F05,
S05,
F04,
S04
Leslie
Hogben's Home Page
Ryan
Martin's Home Page
Discrete Math Seminar 2007-2008. Updated by Ryan Martin: 2007 Jun. 26.