KAIST Discrete Math Seminar

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.

Given graphs H₁,…, H_k, a graph G is (H₁,…, H_k)-free if there is a k-edge-colouring of G with no H_i in colour-i for all i in {1,2,…,k}. Fix a function f(n), the Ramsey-Turán function rt(n,H₁,…,H_k,f(n)) is the maximum size of an n-vertex (H₁,…, H_k)-free graph with independence number at most f(n). We determine rt(n,K₃,K_s,δ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,K₈,f(n)) has a phase transition at f(n)=Θ(√(n\log n)). We prove that rt(n,K₈,o(√(n\log n)))=n²/4+o(n²), 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.

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.

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.

The chromatic number of a graph is the minimum k such that the graph has a proper k-coloring. It is known that if T is a tree, then every graph with large chromatic number contains T as a subgraph. In this talk, we discuss this phenomena for star-coloring (a proper coloring forbidding a bicolored path on four vertices) and acyclic-coloring (a proper coloring forbidding bicolored cycles). Specifically, we will characterize all graphs T such that every graph with sufficiently large star-chromatic number (acyclic-chromatic number) contains T as a subgraph.