Seminars in April 2011

  • Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society
    Special Session on Graph Theory – 2011 spring Meeting of the Korean Mathematical Society
    April 30, 2011, 9:00-11:40
    Asan Science Building (아산이학관), Korea University (고려대), Seoul

    Preregistration deadline: April 11

    Timetable
    • 9:00-9:30 Sang-il Oum (엄상일),  KAIST : Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
    • 9:30-10:00 Sejeong Bang (방세정), Yeungnam University : Geometric distance-regular graphs with smallest eigenvalue -3
    • 10:00-10:10 Break
    • 10:10-11:40 Mark H. Siggers, Kyungpook National University : The H-colouring Dichotomy through a projective property
    • 10:10-10:40 Tommy R. Jensen, Kyungpook National University : On second Hamilton circuits in cubic graphs
    • 11:10-11:40 Jack Koolen, POSTECH : Recent progress of distance-regular graphs

    Organized by Seog-Jin Kim (Konkuk University) and Sang-il Oum (KAIST).

    At 14:00-14:40, there will be an invited talk by Xuding Zhu, Thue choice number of graphs.

    Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
    Sang-il Oum (엄상일)
    Department of Mathematical Sciences, KAIST
    We prove that every infinite sequence of skew-symmetric or symmetric matrices M1, M2, … over a fixed finite field must have a pair Mi, Mj (i<j) such that that Mi is isomorphic to a principal submatrix of the Schur complement of a nonsingular principal submatrix in Mj, if those matrices have bounded rank-width. This generalizes three theorems on well-quasi-ordering of graphs or matroids admitting good tree-like decompositions; (1) Robertson and Seymour’s theorem for graphs of bounded tree-width, (2) Geelen, Gerards, and Whittle’s theorem for matroids representable over a fixed finite field having bounded branch-width, and (3) Oum’s theorem for graphs of bounded rank-width with respect to pivot-minors.
    Geometric distance-regular graphs with smallest eigenvalue −3
    Sejeong Bang (방세정)
    Department of Mathematics, Yeungnam University
    A non-complete distance-regular graph Γ is called geometric if there exists a set C of Delsarte cliques such that each edge of Γ lies in a unique clique in C. In this talk, we determine the non-complete distance-regular graphs satisfying max{3,8(a1+1)/3}<k<4a1+10−6c2. To prove this result, we first show by considering non-existence of 4-claws that any non-complete distance-regular graph satisfying max{3,8(a1+1)/3}<k<4a1+10−6c2 is a geometric distance-regular graph with smallest eigenvalue −3. Moreover, we classify the geometric distance-regular graphs with smallest eigenvalue −3. As an application, 7 feasible intersection arrays are ruled out.
    The H-colouring Dichotomy through a projective property
    Mark H. Siggers
    Department of Mathematics, Kyungpook National University
    The H-colouring Dichotomy of Hell and Nesetril, proved in 1990, is one of the most quoted results in the field of Graph Homomorphisms. It says that H-coloring, the problem of deciding if a given graph G admits an homomorphism to the fixed graph H, is NP-complete if H contains an odd cycle, and otherwise polynomial time solvable.
    In this talk we present a short new proof of this result, recently published, using a new projective property defined for homomorphisms of powers of a graph G onto a graph H.
    On second Hamilton circuits in cubic graphs
    Tommy R. Jensen
    Department of Mathematics, Kyungpook National University
    A classical theorem of Cedric Smith guarantees the existence of a second Hamilton circuit other than a given one in any hamiltonian cubic graph. It is an open problem in complexity theory whether the corresponding search problem is polynomially solvable. We observe that a search algorithm, implicit in Bill Tutte’s nonconstructive proof of Smith’s theorem, has exponential running time. We also mention two possible candidates for search algorithms with polynomial complexity.
    Recent progress of distance-regular graphs
    Jack Koolen
    Department of Mathematics, POSTECH
    I will talk about recent progress of distance-regular graphs.

    (Invited lecture at 2PM)

    Thue choice number of graphs
    Xuding Zhu
    Institute of Mathematics, Zhejiang Normal University, Jinhua, China
    A sequence of even length is a repetition if the first half is identical to the second half. A sequence is said to contain a repetition if it has a subsequence which is a repetition. A classical result of Thue says that there is an infinite sequence on 3 symbols which contains no repetition. This result motivated many deep research and challenging problems. One graph concept related to this result is Thue-colouring. A Thue-colouring of a graph G is a mapping which assigns to each vertex of G a colour (a symbol) in such a way that the colour sequence of any path of G contains no repetition. The Thue-chromatic number of a graph is the minimum number of colours needed in a Thue-colouring of G. Thue’s result is equivalent to say that the infinite path has Thue-chromatic number 3. It is also known that the Thue-chromatic number of any tree is at most 4.
    Thue-choice number of a graph G is the list version of its Thue-chromatic number, which is the minimum integer k such that if each vertex of G is given k-permissible colours, then there is a Thue-colouring of G using a permissible colour for each vertex. This talk will survey some research related to Thue Theorem and will show that Thue-choice number of paths is at most 4 and Thue choice number of trees are unbounded.
    Tags:

  • Xuding Zhu (朱緒鼎), Fractional Colouring of Product Graphs
    Fractional Colouring of Product Graphs
    Xuding Zhu (朱緒鼎)
    Institute of Mathematics, Zhejiang Normal University, Jinhua, China
    2011/4/22 Fri 4PM-5PM

    Given two graphs G and H, the categorical product G \times H has vertex set V(G) \times V(H), and two vertices (x,y) and (x’,y’) are adjacent if xx' \in E(G) and yy' \in E(H). The famous Hedetniemi-Lovász Conjecture asserts that teh chromatic number of G \times H equals the minimum of \chi(G) and \chi(H). In this talk, I will sketch a proof of the fractional version of the conjecture, which says that the fractional chromatic number of G \times H equals to the minimum of the fractional chromatic numbers of G and H. This result is then used to prove a conjecture of Burr-Erdős-Lovász on the chromatic Ramsey number of graphs.

    Tags:

  • (Colloquium) Xuding Zhu (朱緒鼎), Circular Colouring of Graphs
    FYI (Department Colloquium)
    Circular Colouring of Graphs
    Xuding Zhu (朱緒鼎)
    Institute of Mathematics, Zhejiang Normal University, Jinhua, China
    2011/4/21 Thu 4:30PM-5:30PM (Room 1501)

    Vertex colouring of graphs is an active research area in graph theory. It has wide applications to practical problems and also has many theoretically deep results and challenging problems. Circular colouring of graphs is a refinement of the conventional vertex colouring of graphs. It has atttract a lot of attention in the past twenty years, and becomes an important branch of chromatic graph theory, with many exciting results and new techniques. This talk gives a survey on research in this area.

    Tags:

  • Seog-jin Kim (김석진), On-line list colouring of complete multipartite graphs
    On-line list colouring of complete multipartite graphs
    Seog-Jin Kim (김석진)
    Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
    2011/4/18 Wed 4PM-5PM</em>
    The well-known Ohba Conjecture says that every graph G with |V(G)|≤ 2χ(G)+1 is chromatic choosable.
    This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for k≥3, the complete multipartite graph K2*(k-1), 3 is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph G with |V(G)|≥ 2χ(G) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer k, the graph K2*k is on-line chromatic-choosable. We then present a minimal function g for which the graph K2*(k-1), 3 is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.
    Tags:

  • Otfried Cheong, A Generalization of Kakeya’s Problem
    A generalization of Kakeya’s problem
    Otfried Cheong
    Department of Computer Science, KAIST
    2011/4/14 Thu 4:30PM-5:30PM
    One version of Kakeya’s problem asks for the smallest convex garden in which a ladder of length one can be rotated fully. The answer to this question was shown to be the equilateral triangle of height one by Pal in 1920.</p>

    We consider the following generalization: Given a (not necessarily finite) family F of line segments in the plane, what is the smallest convex figure K such that every segment in F can be translated to lie in K?

    We show that as in the classic case, the answer can always be chosen to be a triangle. We also give an O(n log n) time algorithm to compute such an optimal triangle if F consists of n line segments.

    Joint work with Sang Won Bae, Hee-Kap Ahn, Joachim Gudmundsson, Takeshi Tokuyama, and Antoine Vigneron.

    Tags:

Monthly Archives