Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

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

Antoine Vigneron, Reachability in a Planar Subdivision with Direction Constraints

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

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

Otfried Cheong, The reverse Kakeya problem

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

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

« Older Entries
Newer Entries »