Jinyoung Park (박진영), Coloring hypercubes

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

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

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.

Antoine Vigneron, Reachability in a Planar Subdivision with Direction Constraints

March 3rd, 2018
Reachability in a Planar Subdivision with Direction Constraints
Antoine Vigneron
School of Electrical and Computer Engineering, UNIST, Ulsan, South Korea
2018/3/27 Tue 5PM
Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Ω(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.

Otfried Cheong, The reverse Kakeya problem

March 2nd, 2018
The reverse Kakeya problem
Otfried Cheong
School of Computing, KAIST
2017/3/20 Tue 5PM
We prove a generalization of Pal’s 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360 degrees inside Q. We also prove a lower bound of Ω(m n2) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.