Posts Tagged ‘MarkSiggers’

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.

Mark Siggers, The structure of near-unanimity graphs

Friday, March 15th, 2013
The structure of near-unanimity graphs
Mark Siggers
Department of Mathematics
College of Natural Sciences
Kyungpook National University
2013/04/12 Fri 4PM-5PM – ROOM 3433
The class of structures that admit near-unanimity functions is of interest in the field of computational complexity as they yield constraint satisfactions problems that are solvable in deterministic log-space. In the literature, there are diverse characterisations near-unanimity structures, but none that make the generation of all such graphs transparent. We present a new description of reflexive graphs and irreflexive symmetric graphs admitting near-unanimity functions. This description brings together many of the known descriptions, and provides a good picture of near unanimity graphs.
This is joint work with Tomas Feder, Pavol Hell, Benoit Larose, Cindy Loten and Claude Tardif.

Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society

Saturday, March 26th, 2011
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

  • 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.

Mark H. Siggers, CSP Dichotomy and the Fibre Construction

Monday, March 30th, 2009
CSP Dichotomy and the Fibre Construction
Mark H. Siggers
Department of Mathematics, Kyungpook National University, Daegu, Korea
2009/04/10 Friday 4PM-5PM (Room 2411)
In recent years Constraint Satisfaction Problems (CSPs) have gained popularity among graph theorists due to the fact that they can be viewed as a generalisation of graph homomorphism problems. An important conjecture in the field is the CSP Dichotomy Classification Conjecture. Much of the recent progress towards a solution to this conjecture has come from the field universal algebra, and the statement of the Classification Conjecture requires a fair bit of algebraic language.

We talk about a recent graph theoretic construction, called the fibre construction, which can be used to get some of the important results achieved with universal algebra. This construction provides combinatorial version of the Classification Conjecture, and allows one to easily address restricted versions of the Conjecture. Further it leads to results unexpected by the universal algebra community.

Much of the material covered is joint work with Jaroslav Nešetřil and László Zádori.