Abstracts -- Discrete Mathematics Day at WPI 2013

Zajj Daugherty, Dartmouth College
Title: The quasi-partition algebra

Abstract: Several diagram algebras (like the group algebra of the symmetric group) arise via studying endomorphisms of tensor spaces that commute with other familiar groups or algebras (like the general linear group). The commutator relationships provide amazing tools for transferring representation theoretic information back and forth, and reveal beautiful combinatorial structure. In this talk, I will define the quasi-partition algebra, which arises as a centralizer algebra for the symmetric group. We will see how to recognize this algebra as a diagram algebra and explore some of its representation theory.
Erica Flapan, Pomona College
Title: Intrinsic properties of graphs embedded in R3

Abstract: Knot theory is the study of the topology of embeddings of simple closed curves in R3. A natural extension of knot theory is the study of the topology of embeddings of graphs in R3. However, in contrast with knots, the structure of a graph can be complex, and this can affect all of its embeddings. If every embedding of a graph has a particular property, then we say that property is intrinsic to the graph. For example, a graph is said to be intrinsically knotted if every embedding of the graph in R3 contains a knot. In this talk we will discuss intrinsic knotting and other intrinsic properties of graphs.

Jack Graver, Syracuse University
Title: When does a curve bound a distorted disk?

Abstract: Consider a local homeomorphism from the unit circle into R2. Can it be extended to a local homeomorphism of the unit disk? If so, is the extension unique up to homotopy? If the image curve has no self-intersections the answer is yes to both questions. If the image curve has self-intersections then we may interpret the curve as a plane graph. Surprisingly the answers to these questions are uniquely determined by the structure of this graph.

Christino Tamon, Clarkson University
Title: Perfect State Transfer on Graphs

Abstract: Imagine one (or more) quantum particle walking on a finite graph. We describe why this is a natural generalization of classical random walk on graphs, why it might even be relevant to quantum computation, and why it is mathematically fun to explore.

Although quantum analogues of classical notions such as mixing and hitting times are known, our focus will be on a notion called perfect state transfer in quantum walk on graphs.

We discuss recent results on perfect state transfer especially in relation to many-particle quantum walk, graph quotients, and equitable partitions.

Santosh Vempala, Georgia Institute of Technology
Title: On the Complexity of Detecting Planted Cliques and other Latent Structures

Abstract: Detecting a large clique (or a dense subgraph) in a graph is well-studied problem, known to be NP-complete even to approximate. A seemingly more tractable scenario is when the base graph is random and a large clique is "planted". The best-known algorithms for this setting can detect cliques of size roughly square-root of the number of vertices in polynomial time, and need superpolynomial time to find smaller planted cliques. Is this inherent?

We find that the answer is yes, at least for a large class of algorithms that one might call "statistical" algorithms. Such algorithms are ubiquitous and well-motivated, e.g., the analysis of large data sets is often based on algorithms that attempt to infer properties or discover structure by evaluating functions on part of the data. What are the limits of such statistical algorithms? To understand this, we consider a broad framework for problems and algorithms over distributions. This definition captures natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for optimization, MCMC etc.

Using this framework, we obtain unconditional lower bounds on the complexity of statistical algorithms for some well-known problems over distributions. These include superpolynomial lower bounds for finding a direction that maximizes the third moment, and for detecting planted cliques (or planted dense subgraphs); the latter nearly matches the current best upper bounds.