Mini-Workshop on Discrete Mathematics and Related Topics
Mini-Workshop on Discrete Mathematics and Related Topics
Dates: 21st November
Venue: Waseda University, Nishi-Waseda campus, Room 02-13 on the 2nd floor of Building 60
Contact: Tsuyoshi Miezaki miezaki (at) waseda.jp
Organizers: Tsuyoshi Miezaki (Waseda University)
Program:
21st November
12:30–12:50: Yosuke Sato (Waseda University)
Graphical design and equitable partition
A graphical design is a graph-theoretic analogue of a spherical design. In this talk, I will discuss how "extremal" graphical designs can be characterized by means of equitable partitions of graphs.
12:50–13:10: Yuki Terada (Waseda University)
Graphical designs of Paley graphs
We give an algebraic proof that Paley graphs do not admit any nontrivial graphical designs.
13:10–13:30: Ryosuke Yamaguchi (Waseda University)
Approximate counting of graph colorings
In this talk, I will introduce the use of Bubley and Dyer’s path coupling technique for approximate counting of graph k-colorings, and discuss how the method may be extended to the more general setting of H-colorings.
13:30–14:00: Jurre van Schie (Waseda University)
A Linear-Time Algorithm for Computing the Minimum Number of Trees to Cover the Edges of Phylogenetic Networks
Phylogenetic networks capture complex evolutionary histories beyond what trees can represent. Simpson asked for the minimum number of embedded subtrees needed to cover all edges of a binary phylogenetic network, studying limited network classes. We address this problem for any directed phylogenetic network, binary or non-binary. We provide two explicit theorems showing that the minimum number k of subtrees required is determined by the maximum out-degree among tree vertices or maximum in-degree among reticulations. Combining these characterizations yields the first linear-time O(∣V∣+∣E∣) algorithm for the MINIMUM TREE-COVER PROBLEM.
14:00–14:30: Kevin Limanta (The University of New South Wales)
Super Catalan Numbers and Polynomial Summation over Unit Circles over Finite Fields
In this talk I will discuss polynomial summation over unit circles over finite fields of odd characteristic. There are nonetheless strong parallels to classical integration theory over a circle, and we show that the super Catalan numbers and closely related rational numbers lie at the heart of both theories, giving a uniform analytic meaning. In the end, I will also give some explorative implication of this result to finite field spherical design.