University of South Florida

College of Arts and Sciences

Search

Menu

Give Now

Title: On Sparse Graphs with High Chromatic Number Speaker: John Theado Time: 2:00pm‐3:00pm Place: CMC 109

The chromatic number \(\chi(G)\) of a graph \(G=(V,E)\) is the smallest number of colors needed to color \(V\) so that no edge \(e \in E\) has endpoints of the same color. Clearly, \(\chi(G)\) is at least the clique number \(\omega(G)\) (the size of the largest clique in \(G\)), and so a graph with large clique number necessarily has large chromatic number. Perhaps surprisingly, the reverse doesn't hold, in general. Indeed, Mycielski constructed triangle-free graphs with arbitrarily high chromatic number, and we will review this ingenious construction. More strongly, a celebrated result of Erdős shows that there are graphs with both arbitrarily high chromatic number and arbitrarily large girth (which implies that these highly chromatic graphs are locally indistinguishable from forests). We also present the proof of Erdős' result, which is now a classical example of the well-known alteration method in probabilistic combinatorics. In the remaining time, we briefly discuss Hadwiger's conjecture, one of the most important conjectures in all of graph theory, which attempts to bound \(\chi(G)\) by a topological variant of \(\omega(G)\).

Title: Two New Knot Invariants Speaker: Edwin Clark Time: 2:00pm‐3:00pm Place: CMC 109

I will review the definition of quandle and the coloring of a knot by a quandle and make the talk as self-contained as possible. Here knots are always oriented and quandles are always finite. It is well-known that if we define \(\mathrm{Col}_Q(K)\) to be the number of colorings of a knot \(K\) by a quandle \(Q\), then \(K\mapsto\mathrm{Col}_Q(K)\) is a knot invariant. However, this invariant has the problem that if \(r(K)\) is the knot \(K\) with orientation reversed and \(m(K)\) is the mirror image of knot \(K\), then it cannot distinguish \(K\) from \(rm(K)\) no matter which quandle \(Q\) is used. To remedy this Masahico Saito, Leandro Vendramin and I, about a year ago introduced a new invariant: Given a quandle \(Q\) and a knot \(P\) then for a given knot \(K\) we define the invariant \(K\mapsto\mathrm{Col}_Q(P\#K)\) where \(P\#K\) is the connected sum of the knots \(P\) and \(K\). For each \(P\) and \(Q\) one obtains a different invariant. It turns out that for suitable \(Q\) and \(P\) this invariant can in many cases (we conjecture all) distinguish \(K\) from \(rm(K)\). One of the problems with this invariant is that to apply it successfully requires searching for a suitable “prefix knot” \(P\) as well as a suitable quandle \(Q\). Recently, working with Larry Dunning and Masahico Saito we discovered a stronger invariant that does all that the invariant \(K\mapsto\mathrm{Col}_Q(P\#K)\) does without needing the prefix knot \(P\). The new invariant is best described by pictures so I will not describe it here. I will just mention that if the quandle \(Q\) used to define it is an abelian extension of a quandle \(X\) by some “2-cocycle” \(\phi:X\times X\to A\), where \(A\) is an abelian group then the new invariant is equivalent to the now famous quandle 2-cocycle invariant (using \(X,A,\phi\)) defined by Masahico and his collaborators around 1999. Our new invariant (1) gives a seemingly more efficient way to compute the quandle 2-cocycle invariant and (2) has the potential of distinguishing some knots that may not be distinguished by the quandle 2-cocycle invariant.

Title: An Euler totient sum inequality Speaker: Brian Curtin Time: 2:00pm‐3:00pm Place: CMC 109

The power graph of a finite group is the undirected graph whose vertices are the group elements and two elements are adjacent if one is a power of the other. We show that the clique number of the power graph of a cyclic group is given by a nice function of elementary number theory. We discuss some properties of this function.

Title: Hierarchical Assembly of Three-Dimensional DNA Structures Speaker: Daniel Cruz Time: 2:00pm‐3:00pm Place: CMC 109

We extend the Tile Assembly Model with signal passing capabilities to three dimensions (called here 3D Active TAM). The DNA motif on which the 3D Active TAM is based is the modified Tensegrity Triangle motif. This motif has been used as a building block for the design and construction of three dimensional crystals and has shown to build rigid rhomboidal structures.

The 3D Active TAM consists of a set of cubes (as tiles) whose sides consist of active or inactive labels (glues) that can assemble at a given “temperature”. Due to the size of the Tensegrity Triangle motif, the theoretical model allows for at most one label, active or inactive, per side (compared to multiple labels allowed in the two dimensional model). In addition, the inactive label is activated by an attachment of a specific side of the cube, hence there are at most three signals (inactive labels) in a cube.

We present a design for the hierarchical growth of an aperiodic, self-similar, three-dimensional structure within the 3D Active TAM.

Title: Discrete Aspects of Morphing and its Application to Precision and Personalized Medicine, Surgical Planning, and Treatment Speaker: Apurva Bhatty Time: 2:00pm‐3:00pm Place: CMC 109

Morphing is the “in-betweening” of information or imagery from discretely sampled data. It consists of warping and blending and requires the selection of a set of corresponding features or points between two or more images, or between a set of images and a “canonical image” or representation: e.g. the standard human body diagram for burn patients, or the Talairach representation of the human brain. I will review the basics of image processing and morphing algorithms involved, presenting examples from 1-dimensional (EKG or HRTF signals), 2-dimensional (DARPA Shredder Challenge images, burn diagrams of the body), 3-d (MRI and CT of the brain), and 4-d (heart beating over time) data sets.

The clinical use of these algorithms is in Precision Medicine and Personalized Medicine where data is fit to the individual subject rather than to an “average subject”. This personalization allows for more accurate matching and the calculation of areas (burn surfaces), volumes (brain regions and tumor volumes), and personalized treatment options, and the generation of animations for training and surgical planning.

I will review graph-based algorithms for feature selection and matrix-based calculations for the image-processing involved with examples in MATLAB.

Title: Affine Automorphisms of Rooted Trees Speaker: Dima Savchuk Time: 2:00pm‐3:00pm Place: CMC 109

We introduce a class of automorphisms of rooted d-regular trees, arising from affine actions on their boundaries viewed as infinite dimensional vector spaces. This class includes, in particular, many examples of self-similar realizations of lamplighter groups. We show that for a regular binary tree this class coincides with the normalizer of the group of all spherically homogeneous automorphisms of this tree; automorphisms whose states coincide at all vertices of each level. We study in detail a nontrivial example of an automaton group that contains an index two subgroup with elements from this class and show that it is isomorphic to the index 2 extension of the rank 2 lamplighter group \(\mathbb Z_2\wr\mathbb Z\). This is a joint work with Said Sidki.

No seminar this week.

Title: Knots and 3-Manifolds Speaker: Mustafa Hajij Time: 2:00pm‐3:00pm Place: CMC 109

The classification of one and two manifolds is elementary. However, 3-manifolds are still not yet completely classified. In this talk I will talk about how knots can be used to parametrize all closed connected oriented 3-manifolds and show how knot theory can be used to shed some light of the classification problem of 3-manifolds.

Title: Dimension Reduction for Big Data Analysis Speaker: Dan Shen Time: 2:00pm‐3:00pm Place: CMC 109

High dimensionality has become a common feature of “big data” encountered in many divergent fields, such as imaging and genetic analysis, which provides modern challenges for statistical analysis. To cope with the high dimensionality, dimension reduction becomes necessary. I first introduce Multiscale Weighted PCA (MWPCA), a new variation of PCA, for imaging analysis. MWPCA introduces two sets of novel weights, including global and local spatial weights, to enable a selective treatment of individual features and incorporation of class label information as well as spatial pattern within imaging data. Simulation studies and real data analysis show that MWPCA outperforms several competing PCA methods.

Second we develop statistical methods for analyzing tree-structured data objects. This work is motivated by the statistical challenges of analyzing a set of blood artery trees, which is from a study of Magnetic Resonance Angiography (MRA) brain images of a set of 98 human subjects. We develop an entirely new approach that uses the Dyck path representation, which builds a bridge between the tree space (a non-Euclidean space) and curve space (standard Euclidean space). That bridge enables the exploitation of the power of functional data analysis to explore statistical properties of tree data sets.

Title: Modules over Infinite Dimensional Algebras Speaker: Sergio R. Lopez-Permouth, Ohio University, Athens Time: 2:00pm‐3:00pm Place: CMC 109

Let \(A\) be an infinite dimensional \(K\)-algebra, where \(K\) is a field and let \(B\) be a basis for \(A\). In this talk we explore a property of the basis \(B\) that guarantees that \(K^B\) (the direct product of copies indexed by \(B\) of the field \(K\)) can be made into an A-module in a natural way. We call bases satisfying that property “amenable” and we explore whether all amenable bases yield isomorphic A-modules. Then we consider a relation (which we name mutual congeniality) that guarantees that two different amenable bases yield isomorphic A-module structures. In contrast with mutual congeniality, proper congeniality is a one-way ticket to translate infinite linear combinations of elements from one basis into linear combinations of another one. We will explore interesting questions that arise in this context. Most of the examples in this talk will come from the very familiar setting of the algebra \(K[x]\) of polynomials with coefficients in \(K\). If time allows, we might discuss some results regarding these notions in other contexts such as Leavitt Path Algebras (this talk is based on a preprint written jointly with Lulwah Al-Essa and Najat Muthana).

Title: The Polya Permanent Problem: New Results and Techniques Speaker: Alex Guterman, Faculty of Mechanics and Mathematics Lomonosov Moscow State University Time: 2:00pm‐3:00pm Place: CMC 109

Two important functions in matrix theory, determinant and permanent, look very similar: $$ \det A = \sum_{\sigma\in\mathfrak{S}_n}\operatorname{sgn}({\sigma}) a_{1\sigma(1)}\dotsm a_{n\sigma(n)} $$ and $$ \operatorname{per} A = \sum_{\sigma\in {\mathfrak S}_n} a_{1\sigma(1)}\cdots a_{n\sigma(n)}; $$ here \(A=(a_{ij})\in M_n(F)\) is a matrix, \(\mathfrak{S}_n\) denotes the set of all permutations of the set \(\{1,2,\dotsc,n\}\). The value \(\operatorname{sgn}(\sigma)\in \{-1,1\}\) is the signum of the permutation \(\sigma\).

While the computation of the determinant can be done in a polynomial time, it is still an open question, if there are such algorithms to compute the permanent. Due to this reason, starting from the work of Polya, 1913, many researchers are investigating different approaches to convert the permanent into the determinant.

The lecture will contain the exposition of this theory during the past century including our recent research results and techniques.

This talk is based on the joint work with Mikhail Budrevich, Gregor Dolinar, Bojan Kuzma and Marko Orel.

Title: What is a gene? How and why computer science helps in answering this question Speaker: Paolo Cermelli, Department of Informatics, Systems and Communication University of Milano-Bicocca Milan, Italy Time: 2:00pm‐3:00pm Place: CMC 109

Large-scale genomic and trascriptomic analysis in eukaryotic genome projects have produced surprising results that have strongly challenged the traditional understanding of genes. In particular, the gene-centric view of molecular biology has been changed in favour of considering function products (proteins and ncRNAs) rather than genes. This novel view is a consequence of some important findings obtained by a widespread use of software tools specifically developped to accomplish the important task of predicting the gene structure from large-scale gene products (i.e. cDNA, EST sequences and RNA-seq).

In this talk, we will discuss the question posed in the title by discussing some challenging computational problems and algorithmic solutions. We will show that some open problems involve the solution of crucial computational issues that are recurrent in various fields of computational biology such as de novo assembly, indexing and graph theory.