University of South Florida
College of Arts and Sciences
Search
Menu
Give Now
Title: Sub(hypergraph) frequency algorithms Speaker: Brendan Nagle Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: Iterated monodromy groups and \(L\)-presented groups Speaker: Dmytro Savchuk Time: 3:05pm‐3:55pm Place: CMC 120
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)\).
Title: A New Approach to Permutation Polynomials over Finite Fields Speaker: Neranga Fernando Time: 3:05pm‐3:55pm Place: CMC 120
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}\).
No seminar this week due to the holiday.
Title: A Duality between Pro-Filters and Varieties of the Form \(V(\Omega(A))\) Speaker: Joseph Van Name Time: 3:05pm‐3:55pm Place: CMC 120
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)\).
Title: Hashing and Indexing of Foreground vs. Background to Speed-up Tiling Puzzle: Solutions Using Distributed Processing Clusters Speaker: Apurva Bhatty Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: LYM Inequalities for Graded Posets Speaker: Lucas Sabalka, Saint Louis University Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: Geometry of a separating curve complex analogue for \(\mathrm{Out}\,\left(F_n\right)\) Speaker: Dmytro Savchuk Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: Genus Range of \(4\)-regular Rigid Vertex Graphs Speaker: Nataša Jonoska Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: Schreier graphs and Schreier Dynamical Systems of Thompson's group \(F\) Speaker: Dmytro Savchuk Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: On some problems in interpolation related to combinatorial algebra Speaker: Boris Shektman Time: 3:05pm‐3:55pm Place: CMC 120
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.
Title: Periodic Graphs: Towards a Definition, Part II Speaker: Greg McColm Time: 3:05pm‐3:55pm Place: CMC 120
Title: Periodic Graphs: Towards a Definition Speaker: Greg McColm Time: 3:05pm‐3:55pm Place: CMC 120
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.