Mathematics
Seminar



Rocky Mountain Algebraic Combinatorics Seminar
Graph Traversal Edit Distance
Hamidreza Chitsaz
Colorado State University (CS)
Many problems in applied machine learning deal with graphs (also called
networks), including social networks, security, web data mining, protein
function prediction, and genome informatics. The kernel paradigm beautifully
decouples the learning algorithm from the underlying geometric space, which
renders graph kernels important for the aforementioned applications.
In this talk, we give a new graph kernel which we call graph traversal edit
distance (GTED). We introduce the GTED problem and give the first polynomial
time algorithm for it. Informally, the graph traversal edit distance is the
minimum edit distance between two strings formed by the edge labels of
respective Eulerian traversals of the two graphs. Also, GTED is motivated
by and provides the first mathematical formalism for sequence coassembly
and de novo variation detection in bioinformatics.
We demonstrate that GTED admits a polynomial time algorithm using a linear
program (LP) in the graph product space. We prove the LP is unimodular;
hence, it is guaranteed to yield an integer solution. Our proof is based on
the homology of graph product spaces. In particular, we show that the
homology groups of graph product spaces are torsion free. A result of
DeyHiraniKrishnamoorthy then gives the result.
Semiextraspecial Groups
Mark Lewis
Kent State University
Extraspecial groups play an important role in group theory. Particularly in
problems involving character degrees. We will show how how extraspecial
groups can be generalized to semiextraspecial groups. We will present some
of the the basic results regarding semiextraspecial groups. Then we focus
on semiextraspecial groups that have an abelian subgroup of maximal
possible order and consider a connection with semifields.
Weber 223
4–6 pm
Friday, February 16, 2018
(Refreshments in Weber 117, 3:30–4 pm)
Colorado State University
This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly.
Anyone interested is welcome to join us at a local restaurant for dinner after the talks.
PDF version
Previous Seminars:
 February 2, 2018
 James B. Wilson,
Anton Betten
 November 10, 2017
 Michael Kinyon,
Petr Vojt\v{e}chovsk\'y
 October 20, 2017
 Eric Moorhouse,
William DeMeo
 October 6, 2017
 Spencer Gerhardt,
Joshua Grochow
 September 22, 2017
 Amanda Schaeffer Fry,
Henry Kvinge
 September 8, 2017
 Peter Mayr,
James B. Wilson
 May 5, 2017
 Ferdinand Ihringer,
Gavin King
 April 21, 2017
 Vladimir D. Tonchev,
Morgan Rodgers
 April 7, 2017
 Jason Williford,
Anton Betten
 March 24, 2017
 Isabella Novik,
Peter Brooksbank
 March 3, 2017
 Jintai Ding,
Curtis Bennett
 February 17, 2017
 Fatma Karaoglu,
Eric Moorhouse
 February 3, 2017
 Tim Penttila,
James B. Wilson
 December 2, 2016
 Jim Fowler,
Andrew Kelley
 November 11, 2016
 Joseph Gersch,
Joshua Maglione
 October 28, 2016
 John MacLaren Walsh,
Henry Adams
 October 14, 2016
 JM Landsberg,
James B. Wilson
 September 30, 2016
 Alexander Hulpke,
Oscar Levin
 September 16, 2016
 Delaram Kahrobaei,
Amit Patel
 June 23, 2016
 Jason Cantarella,
Michal Adamaszek
 April 29, 2016
 Nick Loehr,
Jason Williford
 April 15, 2016
 Alexander Hulpke,
Klaus Lux
 April 1, 2016
 Eamonn O'Brien,
Izabella Stuhl
 February 19, 2015
 James Wilson,
Anton Betten
 December 4, 2015
 Maria Monks Gillespie,
Dane Flannery
 November 13, 2015
 Richard Green,
Tim Penttila
 October 23, 2015
 Christina Boucher,
Sylvia Hobart
 October 9, 2015
 Josh Maglione,
Ghodratollah Aalipour
 September 25, 2015
 Ross McConnell,
Henry Adams
 September 11, 2015
 James B. Wilson,
Tim Penttila
 May 8, 2015
 Amanda Schaeffer Fry,
Peter Brooksbank
 April 24, 2015
 Heide GluesingLuerssen,
Phil DeOrsey
 March 6, 2015
 Felice Manganiello,
Eric Moorhouse
 February 20, 2015
 Anton Dzhamay,
Anton Betten
 February 6, 2015
 Alexander Hulpke,
Morgan Rodgers
 December 5, 2014
 Stefaan De Winter,
Gretchen Matthews
 November 14, 2014
 Greg Coxson,
Tom Dorsey
 October 31, 2014
 Octavio Paez Osuna,
Sylvia Hobart
 October 10, 2014
 Takunari Miyazaki,
Eric Moorhouse
 September 26, 2014
 Elissa Ross,
Anton Betten
 September 12, 2014
 Petr Vojtěchovský,
Alexander Hulpke
 May 9, 2014
 Philip DeOrsey,
Tim Penttila
 April 25, 2014
 William J Martin,
Jason Williford
 April 11, 2014
 Victor Pambuccian,
George Shakan
 March 7, 2014
 Nathan Lindzey,
Jens Harlander
 February 21, 2014
 Ross McConnell,
Anton Betten
 November 22, 2013
 Justin Hughes,
Josh Maglione

Department of Mathematics Fort Collins, Colorado 80523
