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

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm <mccolm (at) usf.edu>document.write('<a href="mai' + 'lto:' + 'mccolm' + '&#64;' + 'usf.edu' + '">Prof. Greg McColm</a>');)

## Monday, December 2, 2019

Title
Speaker

Time
Place

Network Coding, Rank-Metric Codes, and Rook Theory
Alberto Ravagnani
School of Mathematics & Statistics
University College Dublin
2:00pm–2:50pm
CMC 108

Abstract

In a multicast network, one or multiple sources of information attempt to transmit messages to various terminals through several intermediate nodes. In order to maximize the network throughput, the nodes are allowed to recombine the received packets before forwarding them towards the sinks.

In this context, linear spaces of matrices endowed with the rank metric (rank-metric codes) are a good candidate for correcting errors caused by a noise or by an adversarial attack.

In this talk, I will give an introduction to coding theory and network error-correction. I will then discuss various mathematical aspects of the theory of rank-metric, relating these objects to various combinatorial structures (posets, matrices with restricted entries, and rook placements).

## Monday, November 25, 2019

Title
Speaker

Time
Place

Expanding polynomials for sets with additive or multiplicative structure
Cosmin Pohoata
California Institute of Technology
2:00pm–2:50pm
CMC 108

Abstract

Given an arbitrary set of real numbers $$A$$ and a two-variate polynomial $$f$$ with real coefficients, a remarkable theorem of Elekes and Rónyai from 2000 states that the size $$|f(A,A)|$$ of the image of $$f$$ on the cartesian product $$A \times A$$ grows asymptotically faster than $$|A|$$, unless $$f$$ exhibits additive or multiplicative structure. Finding the best quantitative bounds for this intriguing phenomenon (and for variants of it) has generated a lot of interest over the years due to its intimate connection with the sum-product problem from additive combinatorics. In this talk, we will quickly review some of the results in this area, and then discuss some new bounds for $$|f(A,A)|$$ when the set $$A$$ has few sums or few products. If time permits, will also discuss some new results over finite fields.

## Monday, November 18, 2019

No seminar this week.

## Monday, November 11, 2019

Veteran's Day — no seminar this week.

## Monday, November 4, 2019

Title
Speaker
Time
Place

Product-simplicial Complexes on a Word Graph
Lina Fajardo Gomez
2:00pm–2:50pm
CMC 108

Abstract

Words where each symbol appears exactly twice are called double occurrence words (DOWs). Pattern reduction rules in DOWs can simulate DNA recombination processes. Repeatedly applying these rules to remove subwords from a given word generates words that can be arranged in a partially ordered set. This structure can be represented with a graph whose vertices are DOWs connected by an edge if one word can be obtained from the other through a pattern deletion. On this graph, we consider the cell complex consisting of products of directed simplices, which preserves information about the relationships between words. We define a new boundary operator and prove that the new family of cells is closed under it. This allows the computation of homology groups, which can shed some light on the underlying geometry of the data set.

## Monday, October 28, 2019

Title
Speaker
Time
Place

A result on rational functions via curves over finite fields
Annamaria Iezzi
2:00pm–2:50pm
CMC 108

Abstract

We will show how a bound on the number of rational points on a curve defined over a finite field can be used to prove a curious result about rational functions over finite fields. No spoiler here: come to the talk if you want to know more!

This is a joint work with Xiang-dong Hou.

## Monday, October 21, 2019

No seminar this week.

## Monday, October 14, 2019

Title
Speaker
Time
Place

Using sequence graphs to genotype pathogenic repeats in the human genome
Egor Dolzhenko
2:00pm–2:50pm
CMC 108

Abstract

DNA sequencing has revolutionized clinical genetics by enabling a nearly complete assessment of the variation in the human genome. However many medically-important mutations remain elusive to the standard detection methods. Expansions of short tandem repeats form an important class of such hard-to-detect mutations because they cause over 30 neurological disorders including amyotrophic lateral sclerosis (ALS), fragile X syndrome, and Huntington disease.

We describe a computational method for genotyping repeats and detecting pathogenic repeat expansions. The method is based on sequence graphs, which have recently emerged as robust models for capturing local and genome-scale genetic variation. In our method, sequence graphs encode pathogenic variants and the sequence surrounding them; they make it possible to correctly analyze low complexity and highly polymorphic regions and increase the overall genotyping accuracy to levels similar to those found in “normal” regions of the genome.

We applied our method to DNA sequencing data from 3,001 patients who have been previously tested for presence of the repeat expansion causing ALS. Our method correctly classified all (212/212) samples with expansions as either expansions (208) or potential expansions (4). Additionally, 99.9% (2,786/2,789) of the wild type samples were correctly classified as wild type with the remaining three identified as possible expansions.

We will also highlight how this method is being used by the UK's 100,000 Genomes Project Rare Disease Programme and other organizations and academic groups.

## Monday, October 7. 2019

No seminar this week.

## Monday, September 30, 2019

Title
Speaker
Time
Place

An Equivariant Isomorphism Theorem for Arboreal Galois Representations
Giacomo Micheli
2:00pm–2:50pm
CMC 108

Abstract

In this talk we first recall the notion of arboreal Galois representation and then we develop a method to effectively determine the set of primes $$p$$ for which certain arboreal Galois representations are surjective modulo $$p$$. Our method is based on a combination of height bounds on integral points on elliptic curves over function fields in positive characteristic and the ABC theorem for function fields.

Using this technique we prove Jones' conjecture on the surjectivity of the arboreal Galois representation attached to $$f=x^2+t$$ [Conjecture 6.7, Compositio Math. 43 (5) 1108--1126 (2007)].

This is a recent joint work with Andrea Ferraguti.

## Monday, September 23, 2019

No seminar this week.

## Monday, September 16, 2019

Title
Speaker
Time
Place

On connection between Mealy and Moore automata via $$d$$-adic dynamics
Dima Savchuk
2:00pm–2:50pm
CMC 108

Abstract

The ring $$Z_d$$ of $$d$$-adic integers has a natural interpretation as the boundary of a rooted $$d$$-ary tree. Endomorphisms of this tree are in one-to-one correspondence with 1-Lipschitz mappings from $$Z_d$$ to itself as was shown by Anashin. Therefore, to study such mappings we can use the language of endomorphisms of rooted trees and, in particular, the techniques of Mealy automata. In this talk we give an explicit connection between the van der Put series of a 1-Lipschitz mapping from $$Z_d$$ to itself and the structure of an associated Mealy automaton defining this mapping. This gives a way to construct Mealy automata of mappings that are defined by automatic sequences, like Thue-Morse, for example. This is a joint work with Rostislav Grigorchuk.

## Monday, September 9, 2019

Title
Speaker
Time
Place

Combinatorial Algorithms for the Design of Biomolecular Nanostructures
Abdulmelik Mohammed
2:00pm–2:50pm
CMC 108

Abstract

Over the past three decades, nucleic acids have been successfully demonstrated as nanoscale building materials for the assembly of a variety of shapes, patterns, crystals and computing devices. As the scale and complexity of biomolecular nanostructures increase, the need for the algorithmic formulation of design challenges and the automation of design processes becomes more apparent.

In this talk, we present the algorithmic design of DNA and RNA nanostructures based on surface meshes as discrete approximations of target shapes. An Eulerian-tour model is used for unknotted routing of circular DNA strands on mesh skeleta and we review algorithms for such tours. We also discuss a recent approach to spanning-tree based design of 3D RNA nanostructures from single stranded RNA.