banner USF Home College of Arts & Sciences OASIS myUSF USF A-Z Index

USF Home > College of Arts and Sciences > Department of Mathematics & Statistics

Mathematics & Statistics

Discrete Mathematics
(Leader: )

Monday, December 3, 2012

Title
Speaker
Time
Place

Sub(hypergraph) frequency algorithms
Brendan Nagle
3:05pm-3:55pm
CMC 120

Abstract

Let \(F\) be a fixed \(r\)-graph (\(r\)-uniform hypergraph) on \(f\) vertices. Let \(H=H_n\) be a given \(r\)-graph on \(n\) vertices. How quickly can you count the number of induced copies of \(F\) in \(H\)? In particular, how much better than \(O(n^f)\) can you do?

In the case of graphs (\(r=2\)), this problem is well understood, and the best algorithms come from Fast Matrix Multiplication. In the case of hypergraphs (\(r\ge 3\)), only a few partial results are known. We survey both the graph and hypergraph case. We conclude the talk with an elementary proof of the speaker that the induced \(F\)-count in \(H\) can always be done in time \(o(n^f)\), which had been an open question of R. Yuster.

We also survey what happens, in both the graph and hypergraph cases, if one replaces an exact count with a close estimate. When \(r=2,3\) and \(|H|=\Omega(n^r)\), one can give asymptotic estimates on the induced \(F\)-count in \(H\) with surprising improvements to the running time. These details depend, however, on algorithmic versions of (strong) regularity lemmas, and so we omit such proofs.

Monday, November 26, 2012

Title
Speaker
Time
Place

Iterated monodromy groups and \(L\)-presented groups
Dmytro Savchuk
3:05pm-3:55pm
CMC 120

Abstract

A relatively recent discovery (mainly due to Nekrashevych) of the beautiful connection between holomorphic dynamics and groups generated by automata is realized by iterated monodromy groups. Here is a rough idea: with every (nice) \(d\)-fold self-covering of a (nice) topological space \(X\) one can associate the group acting on the tree of the preimages of any point in \(X\) by automorphisms. It can be shown that under certain labeling of the tree this group can be generated by states of an automaton, which, in turn, may be used to understand the structure of the group.

In particular, it is known that many iterated monodromy groups admit finite \(L\)-presentations. \(L\)-presented groups are finitely generated groups that admit a presentation involving finitely many relators and their iterations by substitution. Such presentations are at the first level of complexity after the finite presentations and quite often provide the simplest way to describe a group that is not finitely presented. In this talk I will give an introduction to iterated monodromy groups, including a baby example. Then I will spend some time discussing \(\mathrm{IMG}(z^2+i)\).

Monday, November 19, 2012

Title
Speaker
Time
Place

A New Approach to Permutation Polynomials over Finite Fields
Neranga Fernando
3:05pm-3:55pm
CMC 120

Abstract

Let \(p\) be a prime and \(q=p^k\). A polynomial \(f(x)\in\mathbb{F}_q[{\tt x}]\) is called a permutation polynomial (PP) over finite field \(\mathbb{F}_q\) if it induces a bijection from \(\mathbb{F}_q\) to itself. The polynomial \(g_{n,q}\in\mathbb{F}_p[x]\) defined by the functional equation $$ \sum_{a\in\mathbb{F}_q} (x+a)^n=g_{n,q}\left(x^q-x\right) $$ gives rise to many permutation polynomials over finite fields. We are interested in triples \((n,e;q)\) for which \(g_{n,q}\) is a permutation polynomial of \(\mathbb{F}_{q^e}\). We present recent discoveries of permutation polynomials in form of \(g_{n,q}\).

Monday, November 12, 2012

No seminar this week due to the holiday.

Monday, November 5, 2012

Title
Speaker
Time
Place

A Duality between Pro-Filters and Varieties of the Form \(V(\Omega(A))\)
Joseph Van Name
3:05pm-3:55pm
CMC 120

Abstract

The category of pro-filters is the category of inverse systems of objects of the form \((X,\mathcal{F})\) such that \(\mathcal{F}\) is a filter on the set \(X\). If \(A\) is an infinite set, then let \(\Omega(A)\) to be the algebra with underlying set \(A\) where each function \(f:A^{n}\rightarrow A\) is a fundamental operation on \(A\) and each \(a\in A\) is a fundamental constant. I shall give an equivalence between a full subcategory of the category of pro-filters and the variety \(V(\Omega(A))\) generated by \(\Omega(A)\).

Monday, October 29, 2012

Title

Speaker
Time
Place

Hashing and Indexing of Foreground vs. Background to Speed-up Tiling Puzzle: Solutions Using Distributed Processing Clusters
Apurva Bhatty
3:05pm-3:55pm
CMC 120

Abstract

Tiling puzzles may allow only translations (Wang tiles) or both rotations and translations (jigsaw puzzles, shredded documents). Tiling puzzles may have edges that are non-ordered (Wang Tiles) or that have a partial order. I will review some heuristics useful in solving these different classes of tiling puzzles. Using two examples from the DARPA Shredder Challenge Puzzle #5, different ways will be presented that these heuristics (and an algorithm for partially-ordered edges) can be carried out on distributed processing systems. A preliminary result about the likelihood of the existence of multiple solutions based on the number of colors leads to a conjecture about the “difficulty” of the puzzles.

Monday, October 22, 2012

Title
Speaker

Time
Place

LYM Inequalities for Graded Posets
Lucas Sabalka
Saint Louis University
3:05pm-3:55pm
CMC 120

Abstract

The LYM inequality for the boolean lattice says that if you give the subset \(S\) of \(\{1,\dotsc,n\}\) a weight of \(1/{n \choose |S|}\) then the sum of the weights in an antichain is at most \(1\). This fact gives an easy proof of Sperner's Theorem, that the size of a largest antichain in the boolean lattice is \({n \choose n/2}\). In this talk we will discuss what happens when you use other weights on other graded posets. In particular, we will characterize weightings that give an LYM inequality or a strict LYM inequality, and (in some sense) determine when these can be used to find large antichains. If time permits, we will prove a more general version of a sharpening of the LYM inequality due to Aydinian and Peter Erdős, which is itself a generalization of a theorem of Ahlswede and Zhang. For the most part, these results follow easily by adapting proof techniques from previously know special cases. This talk will be accessible to graduate students.

Monday, October 15, 2012

Title
Speaker
Time
Place

Geometry of a separating curve complex analogue for \(\mathrm{Out}\,\left(F_n\right)\)
Dmytro Savchuk
3:05pm-3:55pm
CMC 120

Abstract

One of the most popular questions about \(\mathrm{Out}\,\left(F_n\right)\) — a group of outer automorphisms of a free group of rank \(n\) — is the construction of a Gromov hyperbolic space on which \(\mathrm{Out}\,\left(F_n\right)\) naturally acts, extending the deep analogy between \(\mathrm{Out}\,\left(F_n\right)\), mapping class groups, and linear groups. Each mapping class group naturally acts on a curve complex of the surface, which is hyperbolic due to a celebrated theorem by Masur and Minsky. Many spaces which could serve as an analogue for this space were proposed in recent years. We will define some of them and concentrate mostly on a space named the “Edge Splitting Graph” (also known as “Free Factorization Graph”). The main outcome of our work is that this space in not hyperbolic, so it should not be considered as a good analogue to curve complex. I will give some background and introduce the ideas and some techniques used in the proof. This is a joint work with Lucas Sabalka.

Monday, October 8, 2012

Title
Speaker
Time
Place

Genus Range of \(4\)-regular Rigid Vertex Graphs
Nataša Jonoska
3:05pm-3:55pm
CMC 120

Abstract

Graphs with \(4\)-valent and \(1\)-valent rigid vertices, called assembly graphs, have been used to model homologous DNA recombination. We study the topological complexity of spatial embeddings of assembly graphs through studying the genus ranges of these graphs as a function of the number of vertices in the graphs. We show several observations about the genus ranges and state a couple of conjectures.

Monday, October 1, 2012

Title
Speaker
Time
Place

Schreier graphs and Schreier Dynamical Systems of Thompson's group \(F\)
Dmytro Savchuk
3:05pm-3:55pm
CMC 120

Abstract

Schreier graphs are graphs constructed from the action of a group on a set that encode orbits. These graphs are direct generalizations of the Cayley graph of a group. For Thompson's group \(F\), one of the motivations for considering Schreier graphs comes from the most famous question about this group: whether or not Thompson's group \(F\) is amenable (which was very recently announced to have a positive answer). We discuss amenability and consider some examples. We then construct the Schreier graphs for the action of Thompson's group \(F\) on the Cantor set with respect to the standard generating set, classify these graphs up to isomorphism, and study the corresponding Schreier dynamical systems.

Monday, September 24, 2012

Title
Speaker
Time
Place

On some problems in interpolation related to combinatorial algebra
Boris Shektman
3:05pm-3:55pm
CMC 120

Abstract

In hope to solicit interest, advise and/or cooperation from the participants of the seminar, I will outline several problems that I came about through my work in multivariate interpolation. These problems turned out to be closely related to algebraic questions on hyperplane arrangements. I will talk about what little (and it is very little) results I have and what I would like to know and not afraid to ask.

Monday, September 17, 2012

Title
Speaker
Time
Place

Periodic Graphs: Towards a Definition, Part II
Greg McColm
3:05pm-3:55pm
CMC 120

Monday, September 10, 2012

Title
Speaker
Time
Place

Periodic Graphs: Towards a Definition
Greg McColm
3:05pm-3:55pm
CMC 120

Abstract

In textbooks, definitions are often taken for granted and the elbow grease is poured into theorems and occasionally examples. But a lot of effort goes into getting the right definitions. We look at one case study: the definition of “periodic graphs”. Intuitively, a periodic graph should be a graph embedded in a Euclidean space such that for some basis of that space, the corresponding translations induce automorphisms of that graph. But there is more to it than that.