Archive for the ‘2015’ Category

Brendan Rooney, Colourings, Vector Colourings and Cores

Friday, October 9th, 2015
Colourings, Vector Colourings and Cores
Brendan Rooney
Department of Mathematical Sciences, KAIST
2015/10/28 Wed 5PM-6PM

A k-colouring of a graph G is a partition of V(G) into k independent sets. The chromatic number χ(G) is defined as the smallest k so that G has a k-colouring. Alternatively, we can view colourings as homomorphisms to complete graphs, and define χ(G) to be the smallest k so that there is a homomorphism from G to Kk. The variants of χ(G) (for example, fractional chromatic number) are defined by replacing the complete graph Kk with a representative of a different class of graphs (for example, Kneser graphs).

In this talk, we will consider the vector chromatic number of a graph. A vector colouring of a G is a map from V(G) to vectors in Rm (for some m). The goal is to map adjacent vertices to vectors that are far apart. We will look at representations of a graph on its least eigenspace as examples of vector colourings. For distance-regular graphs, these colourings are optimal. Furthermore, we give a method for determining if these colourings are unique. This leads to proofs that certain classes of distance-regular graphs are all cores.

[Colloquium] Choongbum Lee (이중범), Ramsey numbers of graphs

Thursday, September 3rd, 2015
Ramsey numbers of graphs
Choongbum Lee
Department of Mathematics, UCSD, San Diego, CA, USA
2015/09/10 Thu 4:15PM-5:15PM
The Ramsey number of a graph G is the minimum integer n for which every edge coloring of the complete graph on n vertices with two colors admits a monochromatic copy of G. It was first introduced in 1930 by Ramsey, who proved that the Ramsey number of complete graphs are finite, and applied it to a problem of formal logic. This fundamental result gave birth to the subfield of Combinatorics referred to as Ramsey theory which informally can be described as the study of problems that can be grouped under the common theme that “Every large system contains a large well-organized subsystem.”
In this talk, I will review the history of Ramsey numbers of graphs and discuss recent developments.

Madhu Sudan, Reliable Meaningful Communication

Monday, August 3rd, 2015

FYI: A seminar organized by Prof. Jinwoo Shin.

Reliable Meaningful Communication
Madhu Sudan Microsoft Research New England / MIT, Cambridge, MA, USA
2015/08/06 Thu 3PM Room 102, Bldg. N1.
Around 1940, engineers working on communication systems encountered a new challenge: How can one preserve the integrity of digital data, where minor errors in transmission can have catastrophic effects? The resulting theories of information (Shannon 1948) and error-correcting codes (Hamming 1950) created a “marriage made in heaven” between mathematics and its applications. On the one hand emerged a profound theory that could measure information and preserve it under a variety of errors; and on the other hand the practical consequences propelled telephony, satellite communication, digital hardware and the internet. In this talk I will give a brief introduction to the history of the mathematical theory of communication and then describe some of my work in this area that focus on efficient algorithms that can deal with large amounts of error, and on communication when sender and receiver are uncertain about each other’s context.

1st Korean Workshop on Graph Theory

Tuesday, July 28th, 2015
1st Korean Workshop on Graph Theory
August 26-28, 2015
KAIST  (E6-1 1501 & 3435)
  • Program Book
  • 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

Tuesday, 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.