Algebraic, Topological and Complexity Aspects of Graph Covers

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

Program

Sunday

• Dieter Kratsch, Universite de Lorraine - Metz, France: Exact exponential time algorithms for restricted graph homomorphism problems
• Problem session

• Excursion

• 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

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.




X
• Jiri Fiala, Charles University: Universality of covering orders

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




X
• Rok Pozar, University of Primorska: Generating solvable covers

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.




X

• Rob Lewis, Open University, UK: Upper bounds for Abelian Cayley and circulant graphs of diameter two

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.




X
• Grahame Erskine, Open University, UK: Search for Large Diameter 2

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.




X
• Jana Siagiova, Slovak University of Technology, Slovakia: Vertex-transitive graphs and maps for the degree-diameter and the degree-girth problems

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.




X
• Jozef Siran, Open University and Slovak Univ. Techn.: TBA
• Jan Kratochvil, Charles University, Prague: Improvement of exact exponential time algorithm for locally injective homomorphisms

Registration & Fees

Please, note, that the deadline for registration is December 15. 2014.
To register, please fill in the

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, Madeira

Transportation to and from the airport will be provided.

Madeira weather information

Organizers