Archive for the ‘2018’ Category

« Older Entries
Newer Entries »

Jinyoung Park (박진영), Coloring hypercubes

Wednesday, May 16th, 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 hypercubes
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 of the number of 3-colorings, the rest cases remained open
so far. In this talk, I will introduce a recent work on the number of
4-colorings, mainly focusing on how entropy can be used in counting.
This is joint work with Jeff Kahn.

Tags:
Posted in 2018, KAIST Discrete Math Seminar | Comments Closed

Eric Vigoda, Learning a graph via random colorings

Tuesday, May 15th, 2018
Learning a graph via random colorings
Eric Vigoda
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2018/6/11 Mon 5PM-6PM
For an unknown graph G on n vertices, given random k-colorings of G, can one learn the edges of G? We present results on identifiability/non-identifiability of the graph G and efficient algorithms for learning G. The results have interesting connections to statistical physics phase transitions.
This is joint work with Antonio Blanca, Zongchen Chen, and Daniel Stefankovic.

Posted in 2018, KAIST Discrete Math Seminar | Comments Closed

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.

Tags:
Posted in 2018, KAIST Discrete Math Seminar | Comments Closed

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.

Tags:
Posted in 2018, KAIST Discrete Math Seminar | Comments Closed

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.

Tags:
Posted in 2018, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »