University of South Florida
College of Arts and Sciences
Search
Menu
Give Now
Title: Network Coding, Rank-Metric Codes, and Rook Theory Speaker: Alberto Ravagnani, School of Mathematics & Statistics University College Dublin Time: 2:00pm‐2:50pm Place: CMC 108
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).
Title: Expanding polynomials for sets with additive or multiplicative structure Speaker: Cosmin Pohoata, California Institute of Technology Time: 2:00pm‐2:50pm Place: CMC 108
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.
No seminar this week.
Veteran's Day — no seminar this week.
Title: Product-simplicial Complexes on a Word Graph Speaker: Lina Fajardo Gomez Time: 2:00pm‐2:50pm Place: CMC 108
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.
Title: A result on rational functions via curves over finite fields Speaker: Annamaria Iezzi Time: 2:00pm‐2:50pm Place: CMC 108
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.
Title: Using sequence graphs to genotype pathogenic repeats in the human genome Speaker: Egor Dolzhenko Time: 2:00pm‐2:50pm Place: CMC 108
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.
Title: An Equivariant Isomorphism Theorem for Arboreal Galois Representations Speaker: Giacomo Micheli Time: 2:00pm‐2:50pm Place: CMC 108
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.
Title: On connection between Mealy and Moore automata via \(d\)-adic dynamics Speaker: Dima Savchuk Time: 2:00pm‐2:50pm Place: CMC 108
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.
Title: Combinatorial Algorithms for the Design of Biomolecular Nanostructures Speaker: Abdulmelik Mohammed Time: 2:00pm‐2:50pm Place: CMC 108
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.