# Research

## Discrete Mathematics

### Friday, December 2, 2005

Title: On the Asymptotic Number of Non-Equivalent $$q$$-Ary Linear Codes
Speaker: Xiang-Dong Hou
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

Two subspaces (linear codes) of $$F_{q}^{n}$$ are called equivalent if one can be obtained form the other through the action of a monomial matrix (a product of a permutation matrix and a diagonal matrix). We confirmed a recent conjecture about the asymptotic number of non-equivalent codes as $$n$$ tends to infinity. If time permits, we will also mention some related results.

### Friday, November 18, 2005

Title: Graphs and Marriages
Speaker: David Nezelek
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

The marriage game concerns two disjoint sets of players, men and women, along with each player's preferences among the acceptable members of the opposite set. The object is to form stable marriages among the players, such that no two players would prefer to leave their mates for each other. We use the directed-graph approach proposed by Balinski and Ratier to demonstrate the existence of stable marriages, and to explore other items of interest.

### Friday, November 4, 2005

Title: Thresholds and the Creation of Random Structures
Speaker: Greg McColm
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

Quite by accident, the models of random structures mathematicians looked at first were models of random assembly. But there is another kind of model: the model in which all the random elements appear at the beginning, and in which all subsequent development is deterministic. We will look at a class of these, the random geometric graphs — which can be problematic with weak thresholds, and surprise us with strong ones.

### Friday, October 28, 2005

Title: Weak Thresholds and the Simulation of Random Structures
Speaker: Greg McColm
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

There are many models of random graphs, and the model of random strings presented last week can simulate many of these. We will see some models of random accretion, and see that by using the model of random strings, we can prove that these models have weak thresholds. We will also look at some open questions.

### Friday, October 21, 2005

Title: Weak Thresholds and the Evolution of Random Structures
Speaker: Greg McColm
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

There are many extant models of random structures, and it is about time that we start organizing them. Towards this end, we present a general model that subsumes many other models of the random assembly of complex structures. For a theme, we look at the question “at what point of the development does the partially assembled structure satisfy criterion θ?” and we find that in dealing with at least ballpark answers, this model provides some readily accessible results.

### Friday, October 14, 2005

Title: Twist Numbers of Links from the Jones Polynomial
Speaker: Matt Williamson
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

In this talk, I will present some basic information about knot theory, which I learned over the summer for a Research Experience for Undergraduate program. My research deals with twist numbers of links, and their relation to the Jones Polynomial. In a paper written by Dasbach and Lin, the twist number of any alternating knot was found to be encoded inside the Jones Polynomial. I extended this theorem to include alternating links, and I also found a way to read two of the Jones Polynomial coefficients from only using the diagram of the alternating link.

### Friday, October 7, 2005

Title: The Spectrum of the DNA Self-Assembly Model with Flexible Tiles
Speaker: Ana Staninska
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

I’ll talk about the spectrum of a given pot with DNA junction molecules, which is another aspect of the model described by Dr. Jonoska in the previous two meetings. In the final pot of an experiment, only complete complexes represent the solution to a given problem while incomplete complexes are wasted material. With careful selection of the proportion of each proto-tile added in the pot we can annul the amount of incomplete complexes. The space of all the distribution vectors of the proto-tile proportions is called the Spectrum of the pot type. The properties of the spectrum will be the main topic of the talk.

### Friday, September 30, 2005

Title: A Computational Model for Self-Assembling Flexible Tiles, Part II
Speaker: Nataša Jonoska
Time: 10:00am‐11:00am
Place: PHY 120

### Friday, September 23, 2005

Title: A Computational Model for Self-Assembling Flexible Tiles
Speaker: Nataša Jonoska
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

A theoretical model for self-assembling tiles with flexible branches will be introduced. An instance of a “problem” is encoded as a pot of such tiles, and a “solution” is encoded as an assembled complete complex without any free sticky ends (called ports), whose number of tiles is within predefined bounds.

We prove that this model of self-assembly precisely captures NP-computability when the number of tiles in the minimal complete complexes is bounded by a polynomial.

### Friday, September 16, 2005

Title: Leonard pairs and Leonard triples
Speaker: Brian Curtin
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

We begin by introducing the notion of a Leonard pair. We briefly discuss their connections to the orthogonal polynomials in the Askey-scheme and examples arising in representation theory.

We shall also discuss our work on the extension of Leonard pairs to Leonard triples.

### Friday, September 9, 2005

Title: Salient Properties of Scale-free Random Graph Processes
Speaker: Dr. Zoran Nikoluski, Charles University
Prague
Time: 10:00am‐11:00am
Place: PHY 120

#### Abstract

Recent empirical studies of the Internet and the WWW have shown statistical similarities between these and other networks, as diverse as the network of phone-calls, power network, citation, and the network of sexual contacts. The extent to which these, so-called, scale-free (scale-invariant) networks have pervaded, influenced, and conditioned the modern society, have prompted the study of scale-free random graph processes. In this talk, we review results pertinent to the three salient characteristics: scale-free degree distribution, small average path length, and large clustering coefficient. We define a fourth characteristic — degree-degree correlation — and obtain a rigorous result using static description of the scale-free random graph process per Barabasi and Albert. Implications of these salient properties to reliable searching, fast data-communication, and strategies for quarantining a disease, will also be addressed.