Automatic structures are structures whose domain and relations are all presented by finite automata. This class of structures is a restriction of the class of computable structures, and is natural when we consider the case of comptuation with fixed finite resources. All automatic structures have decidable first order theory. This might suggest that they are simple, and perhaps uninteresting as structures. However, we use certain model theoretic measures of complexity to show that automatic structures are as complicated as possible. One such measure is Scott Rank, which measures the automorphism orbits of the structure. We show that for each ordinal less than or equal to omega_1^CK+1, there is an automatic structures whose Scott Rank is that ordinal. This is the same result one sees in the larger class of computable structures. The proof in the automatic structures case uses embeddings of computable structures via configuration space of the corresponding Turing machines. A similar technique can be used to show that there are automatic trees with Cantor-Bendixson rank at any computable ordinal. Again, this result is surprising in that it matches that for computable structures.

This is joint work with B. Khoussainov.

The goal of this talk is to discuss a quantitative measure of how "efficiently connected" a given graph is, and to give examples of families of graphs that are very efficiently connected. To see what this means, think of the problem of efficient network design: if one imagines a graph to represent a computer network with the vertices being computers and the edges being network connections, then one would like to maximize the flow of information through the network while minimizing the cost of building the network. There is a class of graphs, appropriately called expander graphs, that solves this problem extremely well. Moreover, as a special case of expander graphs we have the Ramanujan graphs, which in some sense are the optimal examples of expander graphs. In our talk we will explain these concepts and give some examples of Ramanujan graphs.
Comments: Free Refreshments

We will describe the contrast between model theoretic consequences of Martin's axiom and WGCH ($2^n < 2^{n+1}$). Here are two results of Shelah.

Theorem 1. (WGCH) If an AEC has few models in power $aleph_1$ it is $omega$-stable and has the amalgamation property in $aleph_0$.

Theorem 2. (Martin's Axiom) There is a sentence of $L_{omega_1,omega}$ that is $aleph_1$-categorical but fails amalgamation in $aleph_0$ and is not $omega$-stable.

We will sketch the proof of the second result.

A more general discussion of graduate study and careers in biostatistics will be included, aimed particularly at math majors.

Note: The speaker is a UConn alumnus (B.S. Mathematics, 1987).
Comments: Free Refreshments

The film is 126 minutes long. Free pizza and soda will be offered.

Note the room: MSB 118. You can get there using the elevators in MSB across from Jorgenson (not the elevators near the parking garage). Take the elevator to the 1st floor and take a right.
Comments: Free Refreshments

Given a class of structures K, it is common in model theory to call a structure pseudo-K if it satisfies all first-order statements true in (every structure from) K. Examples are pseudofinite groups and pseudofinite fields. Also it is well known that if a ring is not right coherent, it has pseudoflat left modules that are not flat.

Call a structure quasi-K if it satisfies all positive primitive implications true in K. Clearly pseudo-K implies quasi-K. In Crawley-Boevey's terminology, the full category of all quasiflat modules is the smallest definable subcategory containing all flat modules (over a given ring). The class of quasiflat modules is in some precise sense generated by the closed subset of the Ziegler spectrum corresponding to the flat modules.

I will explain the relationship between quasiflat and pseudoflat modules. This is joint work with Ivo Herzog.

In my talk, I will give many examples of such recurrences and describe the patterns found in them. Certain of these families are connected to the combinatorics of triangulations of polygons, and I will also make these connections explicit.
Comments: Free Refreshments

Recent work shows that the “complexity” of computing lexicographically with a curve in generic coordinates is governed by the singularities of a generic projection. I will discuss joint work with Aldo Conca treating a special case of this phenomenon and remark upon the general situation.

The theory of o-minimal structures gained much attention and inspiration after Wilkie's discovery that the real field with exponentiation is model complete and o-minimal. One subsequent thread of research culminated in Speissegger's notion of Pfaffian closure, which provides a powerful way of obtaining new o-minimal structures. This method generates o-minimal expansions of o-minimal structures by integrating definable 1-forms.

One limitation of this result is that it requires the underlying field to be that of the real numbers. In my thesis, I found a way to extend Speissegger's work to a more general class of real closed fields. In turn, this added generality has consequences back in the real case.

We will describe an elementary way to obtain many subgroups with finite index, using congruences. It turns out that not all subgroups of finite index can be described by congruence conditions, and to construct counterexamples will involve a clever application of the Chinese remainder theorem and the Jordan-Holder theorem.
Comments: Free Donuts (courtesy of GSS)

At this information session, you will get an in-depth look into the experience in Teach for America and hear about the impact that math-oriented majors can make!

Today, more than 5,000 Teach For America corps members work in 26 urban and rural areas profoundly affected by the academic achievement gap. They are working extraordinarily hard to ensure their students achieve academic success - despite the challenges they face growing up in low-income communities. Teach For America alumni are working from all sectors to effect the fundamental changes necessary to ensure educational equity in our country. Join the more than 12,000 outstanding individuals of all academic backgrounds and professional ambitions who have impacted the lives of nearly 3 million students across the country. Full first-year teacher salary and benefits, transitional grants and loans will be described.

Teach For America's next application deadline is Friday, January 4. Apply now to become part of the 2008 Teach For America corps at www.teachforamerica.org/online
Comments: Free Refreshments

1. If f(z) is a rational function with rational coefficients and c is an initial rational number, under what circumstances can the set of iterates {c, f(c), f(f(c)), f(f(f(c))), ...} contain infinitely many integers?
2. For a given rational function f(z) with rational coefficients, how many initial rational values c have a finite set of iterates?