Georgia Institute of Technology College of Sciences

I will talk about a connection between graph theory and sutured Floer homology. In fact, there is a one to one correspondence between hypergraphs of a planar bipartite graph and the dimension of sutured Floer homology of a complement of a neighborhood of special alternating link In a three sphere. This is based on the work of Juhas, Kalman and Rasmussen.

A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. In the context of genomics, DOWs and operations on DOWs have been used in studies of DNA rearrangement. By modeling the DNA rearrangement process using DOWs, it was observed that over 95% of the scrambled genome of the ciliate Oxytricha trifallax could be described by iterative insertions of the ``repeat pattern'' and the ``return pattern''. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW w, we characterize the structure of  w which allows two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively.

For online optimization, the input instance is revealed in a sequence of steps and, after each step, the algorithm has to take an immediate and irrevocable decision based on the previous inputs. Online algorithms produce a sequence of decisions for such problems without the complete information of the future. In the worst-case analysis of online optimization problems, sometimes, it is impossible to achieve any bounded competitive ratio. An interesting way to bypass these impossibility results is to incorporate a stochastic component into the input model. In the random-order arrival model, the adversary specifies an input instance in advance but the input appears according to a random permutation. The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. In this talk, we will present improved competitive algorithms under random-order arrival for these two problems. This is joint work with Susanne Albers and Leon Ladewig.

The space of degree-n complex polynomials with distinct roots appears frequently and naturally throughout mathematics, but its shape and structure could be better understood. In recent and ongoing joint work with Jon McCammond, we present a deformation retraction of this space onto a simplicial complex with rich structure given by the combinatorics of noncrossing partitions. In this talk, I will describe the deformation retraction and the resulting combinatorial data associated to each generic complex polynomial. We will also discuss a helpful comment from Daan Krammer which connects our work with the ideas of Bill Thurston and his collaborators.