Fall 2015 – Algebra and Discrete Math (ADM) Seminar

Fall 2015

Thursdays 3:30-4:30 – Room M-102

Organizers:
Felice Manganiello (manganm@clemson.edu)
Gretchen L. Matthews (gmatthe@clemson.edu)

[divider]

Date Talk
Aug. 27 [toggle_box]
[toggle_item title=”Warren Adams – Clemson University” active=”true”]
A General Theory for Computing Attractive Representations of Nonconvex Optimization Problems [divider]
More than one mathematical representation can accurately depict a decision problem. Success in obtaining optimal solutions, however, often depends upon the formulation selected. Since challenging nonconvex optimization problems are typically solved by using linear programming relaxations as tools to compute bounds for eliminating inferior solutions, “attractive” representations tend to be characterized by the accuracy of their relaxations. This importance of relaxation strength is well documented within the Operations Research literature, where numerous authors have suggested methods for acquiring strength. The posed methods are often problem dependent, relying on the exploitation of specific structures.
This talk presents a general theory for deriving representations with tight relaxations. The fundamental idea is to recast a given problem into higher-dimensional spaces by automatically generating auxiliary variables and constraints. Strength is garnered via suitable mathematical identities. The talk begins with an introduction to the importance of relaxation strength, and then highlights contributions and challenges relative to the progressively more general families of mixed-binary, mixed-discrete, and general nonconvex programs. Ongoing research is discussed.[/toggle_item]
[/toggle_box]
Sept. 10 [toggle_box]
[toggle_item title=”Robert Jamison – Clemson University” active=”false”]
Local Closures on Graphs[divider]
Given a graph (V,E), an arc in G is a symbol of the form S $\mapsto$ v where S is some set of vertices and v a vertex. Given a set A of arcs, a set C of vertices is A-closed provided v $\in$ C whenever S $\subseteq$ C for all arcs S $\mapsto$ v in A. A simple example is geodesic convexity: we have all arcs of the form {x,y} $\mapsto$ v whenever v lies on a shortest path from x to y. In this example, tails S of the arcs are rather stretched out. This talk will focus on the opposite case where the tails S lie in neighborhoods.
[/toggle_item]
[/toggle_box]
Sept. 22 (Tuesday) [toggle_box]
[toggle_item title=”Jon Lee – IOE, U Michigan (joint ADM and OR seminar)” active=”false”]
Comparing polyhedral relaxations via volume[divider]
With W. Morris in 1992, I introduced the idea of comparing polytopes relevant to combinatorial optimization via calculation of n-dimensional volumes. I will review that and related work and describe some new work, with E. Speakman, relevant to the spatial branch-and-bound approach to global optimization. In that work, we calculate exact expressions for 4-dimensional volumes of natural parametric families of polytopes relevant to different convex relaxations of trilinear monomials. As a consequence, we have practical guidance: (i) for tuning an aspect of spatial branch-and-bound implementations, (ii) at the modeling level.
[/toggle_item]
[/toggle_box]
Sept. 24 [toggle_box]
[toggle_item title=”Benton Duncan – North Dakota State University” active=”false”]
Operator algebras associated to integral domains[divider]
The study of operator algebras is strongly connected to the study of topological dynamics. In particular, given a compact space X and a continuous map T: X -> X there is a natural operator algebra associated to the dynamical system, and properties of the dynamics are associated with algebraic properties of the associated algebra. Recent generalizations consider situations where one studies more than one map acting on the space X. As a way of developing examples and building intuition about such objects I consider a module M over an integral domain D and associate an operator algebra by considering the action of D acting on M. This has motivated consideration of relationships between properties of M and properties of the associated operator algebra. This can be used to provide interesting questions that can be considered for operator algebras. I will survey the study of operator algebras associated to dynamical systems and then focus on the case of an integral domain D acting on a D-module.
[/toggle_item]
[/toggle_box]
Oct. 8 [toggle_box]
[toggle_item title=”Lauren Keough – Davidson College” active=”false”]
Extremal Hypergraphs for Independent Sets[divider]
Given a graph G an independent set is a subset of the vertices no two of which are adjacent. There has been interest recently in maximizing the number of independent sets in graphs. For example, the Kahn-Zhao theorem gives an upper bound on the number of independent sets in a d-regular graph.
We will extend the results about independent sets in graphs to hypergraphs. A hypergraph is a generalization of a graph in which an edge can have any size. In an r-uniform hypergraph each edge has size r (so graphs are 2-uniform hypergraphs). An s-independent set is a subset of vertices containing fewer than s vertices from each edge. In this talk we will discuss 1-independent sets and r independent sets in r-uniform hypergraphs and 2-independent sets in 3-uniform hypergraphs.
[/toggle_item]
[/toggle_box]
Oct. 22 [toggle_box]
[toggle_item title=”David Thomson – United States Military Academy West Point” active=”false”]
Some (re-)discoveries in normal bases over finite fields.[divider]
This talk will discuss various results in normal bases over finite fields. The study of normal bases over finite fields took off in the late 1980s, particularly as the emergence of discrete logarithm based cryptography required efficient implementations of field arithmetic in hardware and software.A concrete way to define a normal basis of GF(q^n) over GF(q) is as follows: pick an element A in GF(q^n). If A, A^q, …, A^{q^{n-1}} forms a basis of GF(q^n) over GF(q), the basis is normal. The computational advantage of normal bases is that if an element is expressed in a normal basis representation, its q-th power can be taken as a cyclic shift of its coordinate vector. Exponentiation to any power can be done with square-and-multiply methods.

In this talk, I will outline some of the difficulties of using normal bases, spawning work into describing normal bases of “low complexity”. The so-called “optimal” normal bases were characterized by (Clemson’s own — though then at Waterloo) Gao and H. W. Lenstra, but unfortunately they do not exist for all extensions, and in practice even NIST standards often prescribe non-optimal normal bases. I’ll touch on a couple of my own contributions in this area.

I will also talk about a generalization of normal elements over finite fields, called k-normal elements. Once I arrived at a more pleasing description of k-normals than we originally formulated, I realized I had come full-circle to some work of Gao and others on normal bases in the 90s.[/toggle_item]
[/toggle_box]

Nov. 3 (Tuesday) [toggle_box]
[toggle_item title=”Ezra Miller – Duke University (joint AGNT and ADM seminar)” active=”false”]
Multigraded moduli from fruit flies[divider]
Modules over polynomial rings can arise directly from fundamental biological problems, such as what mechanisms drive the topological variation in fruit fly wing veins. Persistent homology uses multigraded modules to summarize the embedded planar graphs that represent wing veins. Statistical considerations then elicit new kinds of geometric and combinatorial questions about such modules and their moduli. Most of this talk will be spent on the background, including especially an introduction to persistent homology and its reduction to commutative algebra. No prior familiarity with evolutionary biology, or topological data analysis, or multigraded commutative algebra will be assumed.[/toggle_item]
[/toggle_box]
Nov. 5 [toggle_box]
[toggle_item title=”Dustin Cartwright – University of Tennessee Knoxville” active=”false”]
A quantitative version of Mnev’s theorem
[divider]
A matroid is a combinatorial structure recording all incidences between vectors in a fixed vector configuration and the linear spaces spanned by subsets of vectors. Mnev’s theorem says that realization spaces of matroids can be as complicated as arbitrary systems of polynomial equations, in terms of singularities and in terms of finding rational solutions. I will give some background on this theorem and then talk about a version of Mnev’s theorem over the integers, for which the size of the matroid can be bounded in an explicit way.[/toggle_item]
[/toggle_box]
Nov. 19 [toggle_box]
[toggle_item title=”Brandon Goodell – Clemson University” active=”false”]
A Functorial Look at Factorization[divider]
Highly pathological examples of integral domains may be constructed with polynomial extensions and localizations. Due to this, despite that integral domains are nicely behaved, many methods of tackling these domains seem insufficient. One unifying approach to modern mathematics is to use representations: study some category, C, through a functorial looking glass into or out of a well-known category, D. By studying the functors into and out of C or its dual, we gain insight into C. The method is ubiquitous. For example, one may define presheaves as certain functors from the dual of C to the category of sets. For another example, one may consider real linear representations of a category, which are precisely the functors from C to the category of real vector spaces. In this talk, we present a functorial look at integral domains by regarding the group of divisibility as a functor, and we present a few results obtained.[/toggle_item]
[/toggle_box]
Dec. 3 [toggle_box]
[toggle_item title=”Justin Allman – Duke University” active=”false”]
Identities of quantum dilogarithm series from quiver representations[divider]
A quiver is a directed graph. A quiver representation is a choice of vector space at each node and linear map along each arrow. We will focus on the special cases when (1) the underlying non-directed graph of the quiver is a Dynkin diagram and (2) the quiver has oriented cycles, but is a product (in an appropriate sense) of Dynkin diagrams. The space of all quiver representations can be stratified in a geometrically meaningful way, and we show that counting the codimensions of these strata is one way to compute the “combinatorial Donaldson–Thomas invariants” introduced by Keller. As the dimensions of the quiver rep- resentations grow, infinitely many of these codimension counts can be organized simultaneously into a single identity among quantum dilogarithm series, which have a rich history unto themselves. Throughout we will focus on examples.
[/toggle_item]
[/toggle_box]