Research

Discrete Mathematics

(Leader: Prof. Greg McColm)

Monday, April 14, 2008

Abstract

We compare several notions of isomorphism for subconstituent algebras. We use Latin Squares and their subconstituent algebras as a source of examples and counter examples.

Monday, April 7, 2008

Abstract

There is an old theorem of Motzkin and Tausski that states that the variety of pairs of \(N\times N\) commuting matrices is irreducible and has dimension \(N\). For three or more commuting matrices it is not so.

There is an open problem: If the dimension of variety of \(k\) \(N\times N\) matrices has dimension \(N\), does it imply that the variety is irreducible? In the talk I will present an elementary proof (joint with Carl de Boor) of the result of Motskin-Tausski, I will present a counterexample to the aforementioned open problem and discuss a number of related open questions.

Monday, March 31, 2008

Abstract

Let \(p\) be an odd prime, \(q=p^n\), \(F_q\) the finite field of order \(q\) and \(F^*_q\) the multiplicative group of \(F_q\). A function \(f\) from \(F_q\) to \(F_q\) is called planar if for every \(u\) in \(F^*_q\), the function \(f(x+u)-f(x)\) is a permutation of \(F_q\). A construction of planar functions requires the answer to the following question: Assume \(t\) divides \(n\). Can every element of \(F^*_q\) be written as a sum of two \(\left(p^{n/t}-1\right)\)st powers in \(F^*_q\)?

When \(t=1\), the answer is trivially “no”.

When \(t=2\), the answer is no except when \(q=9\). (Simple counting)

When \(t>3\), the answer is “yes”. This follows from a well known estimate of the number of solutions of diagonal equations in terms of Gauss sums.

When \(t=3\), the answer is still “yes”, but the proof requires a new approach.

Monday, March 24, 2008

Abstract

This is a generalization of the Heilbronn problem from two dimensions to three dimensions, which can be defined as follows. For any configuration \(S\) of \(n\) points in the unit cube \([0,1]^3\), let \(T(S)\) be the volume of the smallest tetrahedron. The \(3\)D Heilbronn's problem is about determining $$ \Delta(n)=\max T(S) $$ where the maximum is taken over all possible configuration \(S\) of \(n\) points in \([0,1]^3\). It has been proved that \(n^{-3}\log\,n\ll\Delta(n)\). We shall discuss the lower bounds for \(\Delta(n)\) by using two different methods. One is using an incremental construction which gives a bound \(n^{-3.33}\ll\Delta(n)\), and other is using a probabilistic construction which gives a bound \(n^{-3}\ll\Delta(n)\). The incremental construction methods were used by W. M. Schmidt in 1971, and the probabilistic construction is from N. Alon and J. Spencer's probabilistic methods and later generalized by G. Barequet for higher dimensions.

Monday, March 17, 2008

There will be no seminar this week.

Monday, March 3, 2008

Abstract

Several years ago, Dimitris Achlioptas proposed the following model of the evolution of random graphs. Start with a graph \(G_{n,0}\) of \(n\) isolated vertices, and repeat the following:

1. Given the graph \(G_{n,m}\) of size \(m\), randomly and uniformly select a pair of pairs of vertices \(\{u,v\}\) and \(\{x,y\}\), where neither pair represents an edge in \(G_{n,m}\).
2. A player then chooses which pair to add an edge to to get a graph \(G_{n,m+1}\).
3. Go to (1).

We generalize this question to the semigroup model of random processes, and to two-player games (between a Radical who wants to satisfy the property as soon as possible, and a Conservative who wants to delay the satisfaction of the property); using Zermelo's Theorem, we can get (somewhat) optimal strategies for the Conservative and the Radical. We then ask: given (ensembles of somewhat) optimal strategies, do monotone increasing properties necessarily admit weak thresholds? We find that even phrasing the question properly is complicated, but phrased in just the right way, the answer is “yes”.

Monday, February 25, 2008

There will be no seminar this week.

Monday, February 18, 2008

Monday, February 11, 2008

Abstract

I will be giving two talks on computational complexity theory in consecutive weeks. In these talks, I plan to do the following: I will cover some basic concepts in classical complexity theory. I will also introduce few important rules that govern quantum computation and that are relevant for this talk. Next, I will show certain applications of quantum computational techniques in solving classical complexity problems. Some of these applications are from my recent work.

These applications demonstrate that quantum computing not only offers a possibility for an emerging technology but also provides useful mathematical tools to understand classical computation.

I will try to make the talk self-contained and accessible to people with little background in computational complexity theory.

Monday, February 4, 2008

Abstract

The Hilbert matrix \(a_{i,j}=1/(i+j+1)\) plays an important role in numerical analysis. It's inverse has integer entries. We give one-parameter generalizations of the Fibonacci and Lucas numbers denoted by \(\{F_n(\theta)\}\) and \(\{L_n(\theta)\}\), respectively. We evaluate the Hankel determinants with entries \(\{1/F_{j+k+1}(\theta):0\le i,j\le n\}\) and \(\{1/L_{j+k+1}(\theta):0\le i,j\le n\}\). We also find the entries in the inverse of \(\{1/F_{j+k+1}(\theta):0\le i,j\le n\}\) and show that all its entries are integers. Some of the identities satisfied by the Fibonacci and Lucas numbers are extended to more general numbers. All integer solutions to three diophantine equtions related to the Pell equation are also found.

Monday, January 28, 2008

Abstract

In the last Fall 2007 session of the Discrete Math Seminar, the speaker introduced some of the complexities involved with various notions of hypergraph regularity. In this talk, we attempt to resolve some of these technicalities.