Counting primitive lattice points

Abstract: Let G be a region in the plane R2. In this talk we discuss the problem of counting the number of primitive latice points in G, i.e. the number of integer pairs (m,n) in G such that m and n are relatively prime to each other. The density of such points in the plane is known classically to be equal to 6/pi2; however, there are nice convex regions (such as a disk) that can be chosen with arbitrarily large area and yet do not contain any primitive lattice points. The main result of this talk exhibits a class of regions where we can expect to find the number of primitive lattice points being a fixed proportion of the area. We shall also discuss applications to billiards and Duffin-Schaeffer type problems. This talk will be aimed at graduate students, who are strongly encouraged to attend.

Solid angles in rational polytopes

Abstract: The natural generalization of a two-dimensional angle to higher dimensions is called a solid angle. Given a cone K in Rd, the solid angle at its apex is the proportion of space that K occupies. In slightly different words, if we pick a point x in Rd "at random", the solid angle of K is the probability that x lies in K. In this expository talk, we will outline a theory developed by I. G. Macdonald about the sum of the solid angles at all lattice points in a rational polytope. This theory parallels the one of Ehrhart polynomials (lattice-point enumeration in polytopes), with some additional twists that give rise to a surprising symmetry of the counting functions for solid angles. We will also outline a new proof of the Gram Relations, which are the solid-angle analogs of the Euler Relations that give identities for the face numbers of a polytope.

Bergman complexes, Coxeter arrangements, and graph associahedra

Abstract: Tropical varieties play an important role in algebraic geometry. The Bergman complex B(M) and the positive Bergman complex B+(M) of an oriented matroid M generalize to matroids the notions of the tropical variety and positive tropical variety associated to a linear ideal. Our main result is that if A is a Coxeter arrangement of type Phi with corresponding oriented matroid MPhi, then B+(MPhi) is dual to the graph associahedron of type Phi, and B(MPhi) equals the nested set complex of A. In addition, we prove that for any orientable matroid M, one can find mu(LM) different orientations of M such that the coresponding positive Bergman complexes cover B(M).

Spike timing dependent plasticity: input rate normalization for Poisson inputs

Abstract: A well established concept in neuroscience is that many instances of learning involve correlation based, activity dependent, synaptic modification: modification that leads to the result that "neurons that fire together, wire together". Experiments have shown that in some systems, this modification shows surprising dependence on the relative timing of the pre and post-synaptic action potentials. This dependence is known as spike timing dependent plasticity (STDP). An older alternative model of plasticity, the rate based model, does not depend on spike timing but only on the relative spike rates of pre and postsynaptic neurons. This model, when coupled with an added normalization assumption, has been used to explain many biological observations. In this talk, we rigorously analyze the STDP model. We consider the situation of n input neurons connected to one output neuron. Under mild assumptions about the learning rule and the spiking model, we analyze the situation where the input spike trains are uncorrelated Poisson processes. We prove that learning will send an individual synapse to its minimum or maximum weight. Specializing to a particular spiking model and learning rule, we prove that learning normalizes the sum of the input spike rates. Thus we show that, unlike in the rate based model, normalization is built into the STDP model.

Crystal structure on rigged configurations

Abstract: Rigged configurations label the Bethe vectors of a given spin model. According to a bijection by Kirillov and Reshetikhin (generalized by Kirillov, S., Shimozono) rigged configurations correspond to highest weight crystal paths. The natural question arises whether there exist "unrestricted" rigged configurations corresponding to any crystal path, not necessarily highest weight. In this talk we define unrestricted rigged configurations and describe the crystal structure on this set.

Computing Tropical Varieties

Abstract: Algebraic geometry is the study of algebraic varieties, the solution sets to systems of polynomial equations. A recent approach to this study is to associate to each variety V a tropical variety T. T is a polyhedral complex (a union of sets defined by linear equations and inequalities), and hence is often easier to specify than the complicated set V. Yet T preserves many of the important properties of V, including dimension and degree. Roughly, T is obtained by replacing the usual arithmetic operations "+" and "*" by the operations "min" and "+", respectively. I will give an overview of tropical geometry, provide a range of examples, and present some recent work with Anders Jensen, David Speyer, Bernd Sturmfels, and Rekha Thomas. This work focuses on computational aspects such as how to compute T and how many equations are needed to define it. One surprising result is that even when V is a linear subspace of Cn of dimension d, defining its tropical variety T may require roughly (n choose d) equations!

11th Bay Area Discrete Math Day (at UC Davis)

Higher automata and languages of graphs

Abstract: A word from a finite alphabet can be viewed as a one-dimensional cell complex with labeled cells; rational languages are collections of such words recognized by finite state automata. More generally, various constructions from combinatorics and topology can be viewed as cellular manifolds with labeled cells; a knot diagram, for example, can be viewed as a labeled cellular 2-sphere. We will describe a generalization of finite state automata to this setting, and consider its application to languages of graph colorings, flows, and minors.

Column basis reduction, and decomposable knapsack problems

Abstract: We propose a very simple preconditioning method, called column basis reduction (CBR) for integer programs: applying a transformation to the constraint matrix, to make its columns shorter in euclidean norm, and more orthogonal. It generalizes, and simplifies a reformulation method for equality constrained problems recently proposed by Aardal, Hurkens, Lenstra and others. CBR is attractive for two reasons: computationally, the transformation makes many computationally hard problems trivially solvable; and mathematically, its effect can be rigorously analyzed on a fairly wide class of hard IPs, called decomposable knapsack problems. This class generalizes the instances proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra, Cornuejols and others. We prove that 1) they need an exponential number of nodes to solve by branch-and-bound; 2) after the transformation, a constant number of nodes suffice. The key result in the analysis depends on the properties of Lovasz- or Korkhine-Zolotarev basis reduction: it shows that if the reformulation makes the polyhedron of the problem "better aligned" with the coordinate axes. A subclass of decomposable knapsack problems is called cascade problems. They illustrate the surprising fact, that in hard IPs a "thin" direction is sometimes not the best to branch on. A computational study shows that most difficult IPs recently used to test nontraditional IP algorithms--subset sum, strongly correlated knapsack problems, the marketshare problems, and our cascade problems--become easy for a commercial IP solver after our preconditioning is applied. The talk will assume no background in integer programming. Joint work with Bala Krishnamoorthy at Washington State University.

Affine Tableaux and the Double Affine Hecke Algebra

Abstract: The irreducible representations (irreps) of the symmetric group Sn are parameterized by combinatorial objects called "Young diagrams" lambda. A given irrep has a basis indexed by "Young tableaux" of shape lambda. In fact, this basis consists of weight vectors for a commutative subalgebra X of the group algebra C Sn. The double affine Hecke algebra (DAHA) is a deformation of the group algebra of the affine symmetric group, and also contains a commutative subalgebra X. Not every irrep of the DAHA has a basis of weight vectors (and in fact it is quite difficult to parameterize all of its irreps), but if we restrict our attention to those that do, these are parameterized by "affine shapes" lambda/mu and have a basis of X-weight vectors indexed by the "affine tableaux" of that shape. In this talk, we will construct these irreps.

Polynomial Graphs with Applications to Game Theory

Abstract: We introduce a set of conditions a system of polynomial equations in several variables may satisfy, which are encoded in an associated graph, the polynomial graph. We explain a theorem describing the number of solutions to the system in this case, and show how this can be applied to graphical games. Time permitting, we will also describe emergent node tree structures on games, a new model for games in which the players can be hierarchically decomposed into groups, along with a new solution concept for these games which refines Nash equilibria. We describe how the theorem applies to games with ENTs.

Transportation Polytopes: a twenty-year update

Abstract: A transportation polytope consists of all multidimensional arrays of nonnegative numbers that satisfy certain sum conditions on subsets of the entries. They arise naturally in optimization and statistics and have also interest for pure mathematics due to the appearance of permutation matrices, latin squares, magic squares, as lattice points of these polytopes. In this talk we survey recent advances on the understanding of the combinatorics and geometry of these polyhedra. In particular, we try to give a complete report on the status of a long list of open questions last collected in the 1984 monograph by Yemelichev-Kovalev-Kravtsov and the 1986 survey paper of Vlach.