1st Korean Workshop on Graph Theory

July 28th, 2015
1st Korean Workshop on Graph Theory
August 26-28, 2015
KAIST  (E6-1 1501 & 3435)
  • Currently, we are planning to have talks in KOREAN.
  • Students/postdocs may get the support for the accommodation. (Hotel Interciti)
  • Others may contact us if you wish to book a hotel at a pre-negotiated price. Please see the website.
  • We may or may not have contributed talks. If you want, please contact us.
Location: KAIST
  • Room 1501 of E6-1 (August 26, 27)
  • Room 3435 of E6-1 (August 28)
Invited Speakers:

Jinfang Wang, Big Math Data: possibilities and challenges

July 28th, 2015
Big Math Data: possibilities and challenges
Jinfang Wang
Institute: Department of Mathematics and Informatics, Graduate School of Science, Chiba University, Japan.
2015/08/05 Wed 4PM-4:50PM
The computer has influenced all kinds of sciences, with mathematical sciences being no exception. Mathematicians have been looking for a new foundation of mathematics replacing ZFC (Zermelo-Fraenkel set theory with the axiom of choice) and category theory, both of which have been successful to a great extent. Indeed, a theory, known as Type Theory, is rising up as a powerful alternative to all these traditional foundations. In type theory, any mathematical object is represented as a type.
Various formal proof systems, including HOL, Isabelle, Idris, Coq, Agda, are based on this theory. Thanks to this new theory, it is becoming a reality that mathematical reasoning can indeed be digitized. Philosophers, logicians, computer scientists, and mathematicians as well, have been making a great deal of efforts and progresses to formalize various mathematical theories. Recent breakthroughs include, but not limited to, the computer-verified proofs of the Four Color Theorem (2004), the Feit Thomson Theorem (2012), and the Kepler Conjecture (2014).
To formalize the proofs of these theorems, large amount of mathematical theories have been digitized and stored in the form of libraries (analogies of R libraries familiar to our statisticians). For instance, the formal proof of the Feit Thomson Theorem had involved 170,000 lines of codes with more than 15,000 definitions and 4,200 lemmas. These large data, referred to as Big Math Data hereafter, open a new paradigm and present serious challenges for statisticians to analyze a totally different type of data we have never experienced before, namely the mathematical theories. The right figure shows some libraries which form SSReflect, an extension of the interactive theorem prover Coq. There are many other libraries available as the results produced in the process of formalizations of various mathematical theories.
In this talk, I shall give a gentle introduction to Big Math Data, and describe the possible mathematical and statistical challenges for both obtaining and analyzing Big Math Data.

Yaokun Wu, Graph dynamical systems: Some combinatorial problems related to Markov chains

July 28th, 2015
Graph dynamical systems: Some combinatorial problems related to Markov chains
Yaokun Wu
Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China
2015/8/5 Wed 3PM-3:50PM
An order-t Markov chain is a discrete process where the outcome of each trial is linearly determined by the outcome of most recent t trials. The set of outcomes can be modelled by functions from a set V to a set F. The linear influences can be described as t-linear maps. When t=1, the set of linear influences can be conveniently described as digraphs on the vertex set V. Most of our talk is concerned with a combinatorial counterpart of Markov chains, where we can only tell the difference between zero probability and positive probability. We especially focus on the Boolean case, namely F is a 2-element set. This talk is to introduce several easy-to-state combinatorial problems about discrete dynamics, which arise from the combinatorial considerations of Markov chains.

Andreas Galanis, Approximately Counting H-Colorings is #BIS-Hard

June 25th, 2015
Approximately Counting H-Colorings is #BIS-Hard
Andreas Galanis
Department of Computer Science, University of Oxford, Oxford, UK
2015/7/13 Mon 11AM-12PM
We consider the problem of counting H-colorings from an input graph G to a target graph H. (An H-coloring of G is a homomorphism from the graph G to the graph H.)
We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in a important complexity class for approximate counting, and is widely believed not to have an FPRAS. If this is so, then our result shows that for every graph H without trivial components, the H-coloring counting problem has no FPRAS.
This problem was studied a decade ago by Goldberg, Kelk and Paterson. They were able to show that approximately sampling H-colorings is #BIS-hard, but it was not known how to get the result for approximate counting. Our solution builds on non-constructive ideas using the work of Lovasz.
Joint work with Leslie Goldberg and Mark Jerrum.

[Lecture Series] Johann Makowsky, Graph Polynomials

June 17th, 2015
Graph Polynomials
Johann Makowsky
Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
Lecture 1: 2015/07/20 Mon 3:30PM-5:10PM
Lecture 2: 2015/07/21 Tue 3:30PM-5:10PM
Lecture 3: 2015/07/22 Wed 3:30PM-5:10PM
Room: E6-1, Room 2412
Lecture 1: A Landscape of Graph Polynomials.

We introduce the most prominent graph polynomials (characteristic, Laplacian, chromatic, matching, Tutte) and discuss how to compare them.

Lecture 2: Why is the Chromatic Polynomial a Polynomial?

We give an alternative proof for the fact that the chromatic polynomial is indeed a polynomial. From this we introduce generalized chromatic polynomials, and show that this actually represents the most general case; Every (reasonably defined) graph polynomial can be represented as a generalized chromatic polynomial.

Lecture 3: Hankel matrices and Graph Polynomials.

We introduce Hankel matrices of graph paramaters, which generalize Lovasz’ connection matrices. We show that many (but not all) graph polynomials have Hankel matrices of finite rank. We show how to use the Finite Rank Property to show definability/non-definability of graph parameters/polynomials in Monadic Second Order Logic.