The workshop's main focus is on graph coverings and their applications in different areas of theoretical computer science such as models of computation, computational complexity, and algebraic graph theory. The aim of the workshop is to bring together researchers working on these diverse ends of graph coverings, to introduce their approaches and results to one another, and to try to pursue joint research combining these areas. Towards this end we plan a small number of survey talks, several open problem sessions, and ample time for discussions and problem solving...
This is already the seventh workshop in the ATCAGC series and is organized by:
- Department of Informatics, University of Bergen
- Department of Applied Mathematics, Charles University, Prague
Previous workshops were held in:
- Ostravice, Czech republic, 2014
- Bovec, Slovenia, 2013
- Eugene, Oregon, 2012
- Kralova Studna, Slovakia, 2011
- Auckland, New Zealand, 2010
- Finse, Norway, 2009
Honorary Invited Talk
- Split lifts Alexander Malnic, University of Ljubljana and University of Primorska
Confirmed Invited Talks
- On the computational complexity of regular covers by planar graphs Pavel Klavik, Charles University, Prague
- Exact exponential time algorithms for restricted graph homomorphism problems Dieter Kratsch, Universite de Lorraine, Metz
- Dieter Kratsch, Universite de Lorraine - Metz, France: Exact exponential time algorithms for restricted graph homomorphism problems
- Problem session
- Pavel Klavik, Charles University in Prague: On the computational complexity of regular covers by planar graphs
- Peter Zeman, Charles University in Prague: Automorphism Groups of Geometrically Represented Graphs
- Dusan Knop, KAM Charles University: IV-matching is NP-hard
- Aleksander Malnic, Univ. of Ljubljana and Univ. of Primorska: Split lifts
- Jiri Fiala, Charles University: Universality of covering orders
- Rok Pozar, University of Primorska: Generating solvable covers
A large part of algebraic graph theory is devoted to analyzing structural properties of graphs with prescribed degree of symmetry in order to classify, enumerate, construct infinite families, and to produce catalogs of particular classes of interesting graphs up to a certain reasonable size. It is not surprising, then, that the techniques employed in these studies are fairly diverse, ranging from pure combinatorial and computational methods to methods from abstract group theory, permutation groups, combinatorial group theory, linear algebra, representation theory, and algebraic topology. Covering space techniques, and lifting groups of automorphisms along regular covering projections in particular, play a prominent role in this context. A systematic combinatorial treatment of lifting automorphisms has been considered by several authors, yet several important issues still remain to be considered. In view of the fact that structural properties of graphs often rely on the structure and the action of their automorphism groups,one such topic is investigating the structure of lifted groups. Other points of interest are algorithmic and complexity aspects of lifting automorphisms, which have so far received even less attention. In the talk I will review some recent results along these lines. Joint work with Rok Pozar.
We show that partial orders imposed by the existence of locally bijective, injective or surjective, resp. homomorphisms are universal on very narrow classes of graphs like disjoint unions of cycles. We briefly discuss other order related properties like gaps, density, etc. Joint work with Jan Hubiccka and Yangjing Long
We present basic properties of universal covering projections and exploit them in order to develop an algorithm for computing all solvable regular covering projections of a given graph admitting a lift of a given group of automorphisms.
- Rob Lewis, Open University, UK: Upper bounds for Abelian Cayley and circulant graphs of diameter two
- Grahame Erskine, Open University, UK: Search for Large Diameter 2
- Jana Siagiova, Slovak University of Technology, Slovakia: Vertex-transitive graphs and maps for the degree-diameter and the degree-girth problems
- Jozef Siran, Open University and Slovak Univ. Techn.: TBA
- Jan Kratochvil, Charles University, Prague: Improvement of exact exponential time algorithm for locally injective homomorphisms
Abstract The best lower and upper bounds for both Abelian Cayley and circulant graphs of diameter 2 and degree d that are valid for all d are (1/4) d^2+O(d) and (1/2) d^2+O(d) respectively. A method of construction using the direct product of the additive and multiplicative subgroups of a Galois field and a coprime cyclic group has recently been successfully employed to construct families of circulant graphs of diameter 2 for infinite sparse sets of degree d with quadratic coefficient 9/25 and 13/36, and similarly for Abelian Cayley graphs with coefficient 3/8. Attempts to further improve the quadratic coefficient have so far been unsuccessful. In this talk I present generalisations of these graph construction methods. For these categories of circulant and Abelian Cayley graphs a new asymptotic upper bound for the quadratic coefficient of 3/8 is established. Analysis of the orders of the known extremal diameter 2 circulant graphs, up to degree 23, is shown to provide tentative support for a coefficient of 3/8 for the asymptotic upper bound for circulant graphs in general.
The idea of graphs where we allow a mixture of directed and undirected edges received little attention for some years, but has been the subject of recent interest in the degree-diameter problem. In this talk I will discuss some work in progress and partial results in the search for maximal graphs of diameter 2.
A number of constructions of the best currently known graphs for the degree-diameter and the degree-girth problems are vertex-transitive and arise from coverings. In the talk we will give a survey of such constructions and explore their vertex-transitive embeddings.
|Jiri Fiala||Universality of covering orders|
|Jan Arne Telle||TBA|
|Grahame Erskine||Search for Large Diameter 2 Mixed Graphs|
|Peter Zeman||Automorphism Groups of Geometrically Represented Graphs|
|Jana Šiagiová||Vertex-transitive graphs and maps for the degree-diameter and the degree-girth problems|
|Aleksander Malnic||Split lifts|
|Rok Pozar||Generating solvable covers|
|Rob Lewis||Upper bounds for Abelian Cayley and circulant graphs of diameter two|
|Dušan Knop||IV-matching is NP-hard|
Registration & Fees
Please, note, that the deadline for registration is December 15. 2014.
To register, please fill in the registration form.
The costs are estimated to
- 400 euro
- transportation from airport to hotel
- 6 nights stay including breakfasts and lunches
- transportation to Sunday excursion
- transportation to the airport upon departure
Accomodation & Travel Info
Address: Hotel Jardim do Mar, Calheta, MadeiraHotel Jardim do Mar is located in the southwest of Madeira, in Calheta, 45 minutes from the international airport.
Transportation to and from the airport will be provided.
Madeira weather information