Archive for the ‘KAIST Discrete Math Seminar’ Category

(Intensive Lecture Series) Jaehoon Kim, A course in graph embedding

Monday, May 14th, 2018

Intensive Lecture Series

A course in graph embedding
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, Birmingham, UK
2018/6/25-29 10:30AM-12PM, 2:30PM-4PM (Room 3433, Bldg. E6-1)

In this lecture, we aim to learn several techniques to find sufficient conditions on a dense graph G to contain a sparse graph H as a subgraph.

Tentative plan for the course (June 25, 26, 27, 28, 29)
Lecture 1 : Basic probabilistic methods
Lecture 2 : Turan numbers
Lecture 3 : Bipartite Turan numbers and dependent random choice
Lecture 4 : The regularity lemma and its applications
Lecture 5 : Embedding large graphs
Lecture 6 : The blow-up lemma and its applications I
Lecture 7 : The blow-up lemma and its applications II
Lecture 8 : The absorbing method
Lecture 9 : Graph packing problems and iterative absorption I
Lecture 10 : Graph packing problems and iterative absorption II

Michael Dobbins, Grassmanians and Pseudosphere Arrangements

Tuesday, May 1st, 2018

(JOINT DISCRETE MATH & TOPOLOGY SEMINAR)

Grassmanians and Pseudosphere Arrangements
Michael Dobbins
Department of Mathematics, Binghamton University, Binghamton, NY, USA
2018/5/30 Wednesday 5PM
In this talk I will present a metric space of pseudosphere arrangements, as in the topological representation theorem of oriented matroids, where each pseudosphere is assigned a weight. This gives an extension of the space of full rank vector configurations of fixed size in a fixed dimension that has nicer combinatorial and topological properties. In rank 3 these spaces, modulo SO(3), are homotopy equivalent to Grassmanians, and the subspaces representing a fixed oriented matroid are contractible. Work on these spaces was partly motivated by combinatorial tools for working with vector bundles.

Jinyoung Park (박진영), Coloring hypercubes

Tuesday, April 10th, 2018
Coloring hypercubes
Jinyoung Park (박진영)
Department of Mathematics, Rutgers, Piscataway, NJ, USA
2018/06/26 Tuesday 5PM
We discuss the number of proper colorings of the hypercube (the covering graph of the Boolean algebra) given q colors. When q=2, it is easy to see that there are only 2 possible colorings. However, it is already highly nontrivial to figure out the number of colorings when q=3. Since Galvin (2002) proved the asymptotics for the number of 3-colorings, the rest cases remained open so far. In this talk, I will introduce a recent work about the number of 4-colorings, mainly focusing on 1. how entropy can be used in counting and 2. isoperimetric properties of hypercube. This is joint work with Jeff Kahn.

Mark Siggers, The reconfiguration problem for graph homomorpisms

Monday, March 12th, 2018
The reconfiguration problem for graph homomorpisms
Mark Siggers
Department of Mathematics, Kyungpook National University, Daegu
2018/04/03 Tue 5PM
For problems with a discrete set of solutions, a reconfiguration problem defines solutions to be adjacent if they meet some condition of closeness, and then asks for two given solutions it there is a path between them in the set of all solutions.
The reconfiguration problem for graph homomorphisms has seen fair activity in recent years. Fixing a template, the problem Recol(H) for a graph H asks if one can get from one H-colouring of a graph G to another by changing one vertex at a time, always remaining an H-colouring. If the changed vertex has a loop, it must move to an adjecent vertex
Depending on H, the problem seems to be either polynomial time solvable or PSPACE-complete. We discuss many recent results in the area and work towards conjecturing for which H the problem is PSPACE-complete.
This is joint work with Rick Brewster, Jae-baek Lee, Ben Moore and Jon Noel.

Hong Liu, Two conjectures in Ramsey-Turán theory

Thursday, March 8th, 2018
Two conjectures in Ramsey-Turán theory
Hong Liu
Mathematics Institute, University of Warwick, Warwick, UK
2018/4/10 Tue 5PM
Given graphs H1,…, Hk, a graph G is (H1,…, Hk)-free if there is a k-edge-colouring of G with no Hi in colour-i for all i in {1,2,…,k}. Fix a function f(n), the Ramsey-Turán function rt(n,H1,…,Hk,f(n)) is the maximum size of an n-vertex (H1,…, Hk)-free graph with independence number at most f(n). We determine rt(n,K3,Ks,δn) for s in {3,4,5} and sufficiently small δ, confirming a conjecture of Erdős and Sós from 1979. It is known that rt(n,K8,f(n)) has a phase transition at f(n)=Θ(√(n\log n)). We prove that rt(n,K8,o(√(n\log n)))=n2/4+o(n2), answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings. Joint work with Jaehoon Kim and Younjin Kim.