- You are here:
- GT Home
- Home
- News & Events
Series: ACO Alumni Lecture
Hadwiger (Hajos and Gerards and Seymour, respectively) conjectured that the vertices of every graph with no K_{t+1} minor (topological minor and odd minor, respectively) can be colored with t colors such that any pair of adjacent vertices receive different colors. These conjectures are stronger than the Four Color Theorem and are either wide open or false in general. A weakening of these conjectures is to consider clustered coloring which only requires every monochromatic component to have bounded size instead of size 1. It is known that t colors are still necessary for the clustered coloring version of those three conjectures. Joint with David Wood, we prove a series of tight results about clustered coloring on graphs with no subgraph isomorphic to a fixed complete bipartite graph. These results have a number of applications. In particular, they imply that the clustered coloring version of Hajos' conjecture is true for bounded treewidth graphs in a stronger sense: K_{t+1} topological minor free graphs of bounded treewidth are clustered t-list-colorable. They also lead to the first linear upper bound for the clustered coloring version of Hajos' conjecture and the currently best upper bound for the clustered coloring version of the Gerards-Seymour conjecture.
Series: Other Talks
Chun-Hung will discuss his employment experience as an ACO alummus. The conversations will take place over coffee.
Series: Stochastics Seminar
Series: Graph Theory Working Seminar
Erdős
and Nešetřil conjectured in 1985 that every graph with maximum degree Δ
can be strong edge colored using at most 5/4 Δ^2 colors. The conjecture
is still open for Δ=4. We show the conjecture is true when an edge cut
of size 1 or 2 exists, and in certain cases when an edge cut of size 4
or 3 exists.
Series: High Dimensional Seminar
We will try to address a few universality questions for the behavior of large random matrices over finite fields, and then present a minimal progress on one of these questions.
Series: Analysis Seminar
The Bishop-Phelps-Bolloba ́s property for numerical radius says that if we have a point in the Banach space and an operator that almost attains its numerical radius at this point, then there exist another point close to the original point and another operator close to the original operator, such that the new operator attains its numerical radius at this new point. We will show that the set of bounded linear operators from a Banach space X to X has a Bishop-Phelps-Bolloba ́s property for numerical radius whenever X is l1 or c0. We will also discuss some constructive versions of the Bishop-Phelps- Bolloba ́s theorem for l1(C), which are an essential tool for the proof of this result.
Series: PDE Seminar
The Euler-Alignment system arises as a macroscopic representation of the Cucker-Smale model, which describes the flocking phenomenon in animal swarms. The nonlinear and nonlocal nature of the system bring challenges in studying global regularity and long time behaviors. In this talk, I will discuss the global wellposedness of the Euler-Alignment system with three types of nonlocal alignment interactions: bounded, strongly singular, and weakly singular interactions. Different choices of interactions will lead to different global behaviors. I will also discuss interesting connections to some fluid dynamics systems, including the fractional Burgers equation, and the aggregation equation.
Series: Dissertation Defense
The length LC_n of the longest common subsequences of two strings X = (X_1, ... , X_n) and Y = (Y_1, ... , Y_n) is a way to measure the similarity between X and Y. We study the asymptotic behavior of LC_n when the two strings are generated by a hidden Markov model (Z, (X, Y)) and we build upon asymptotic results for LC_n obtained for sequences of i.i.d. random variables. Under some standard assumptions regarding the model we first prove convergence results with rates for E[LC_n]. Then, versions of concentration inequalities for the transversal fluctuations of LC_n are obtained. Finally, we outline a proof for a central limit theorem by building upon previous work and adapting a Stein's method estimate.
Series: Dissertation Defense
The Four Color Theorem states that every planar graph is 4-colorable. Hajos conjectured that for any positive integer k, every graph containing no K_{k+1}-subdivision is k-colorable. However, Catlin disproved Hajos' conjecture for k >= 6. It is not hard to prove that the conjecture is true for k <= 3. Hajos' conjecture remains open for k = 4 and k = 5. We consider a minimal counterexample to Hajos' conjecture for k = 4: a graph G, such that G contains no K_5-subdivision, G is not 4-colorable, and |V (G)| is minimum. We use Hajos graph to denote such counterexample. One important step to understand graphs containing K_5-subdivisions is to solve the following problem: let H represent the tree on six vertices, two of which are adjacent and of degree 3. Let G be a graph and u1, u2, a1, a2, a3, a4 be distinct vertices of G. When does G contain a topological H (i.e. an H-subdivision) in which u1, u2 are of degree 3 and a1, a2, a3, a4 are of degree 1? We characterize graphs with no topological H. This characterization is used by He, Wang, and Yu to show that graph containing no K_5-subdivision is planar or has a 4-cut, establishing conjecture of Kelmans and Seymour. Besides the topological H problem, we also obtained some further structural information of Hajos graphs.
Series: Geometry Topology Seminar
It is well known that two knots in S^3 are ambiently isotopic if and only if there is an orientation preserving automorphism of S^3 carrying one knot to the other. In this talk, we will examine a family of smooth 4-manifolds in which the analogue of this fact does not hold, i.e. each manifold contains a pair of smoothly embedded, homotopic 2-spheres that are related by a diffeomorphism, but are not smoothly isotopic. In particular, the presence of 2-torsion in the fundamental groups of these 4-manifolds can be used to obstruct even a topological isotopy between the 2-spheres; this shows that Gabai's recent ``4D Lightbulb Theorem" does not hold without the 2-torsion hypothesis.
