Algebraic, Topological and Complexity Aspects of Graph Covers
& Winter School in Harmonic Functions on Graphs and Combinatorial Designs

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

Part of the program will consists of a series of introductory lectures on harmonic functions on graphs and on combinatorial designs aimed at PhD. students and young researchers.

This is already the sixth workshop in the ATCAGC series and is organized by:

• Czech Mathematical Society, section of The Union of Czech Mathematicians and Physicists (JCMF)
• Slovak Mathematical Society, section of The Union of Slovak Mathematicians and Physicists (JSMF)
• Matej Bel University, Banska Bystrica
• Department of Applied Mathematics, Charles University, Prague

Previous workshops were held in:

• Bovec, Slovenia, 2013
• Eugene, Oregon, 2012
• Kralova Studna, Slovakia, 2011
• Auckland, New Zealand, 2010
• Finse, Norway, 2009

ATCAGC Talks & Contributions

• Rotary and regular maps with simple underlying graphs Marston Conder, University of Auckland, New Zealand

A regular map is a symmetric embedding of a graph (or multigraph) on some closed surface. This talk concerns the genus spectrum for such maps on orientable surfaces, with SIMPLE underlying graph. It is known that for some positive integers g, there is no orientably-regular map of genus g for which both the map and its dual have simple underlying graph, and also that for some g, there is no such map (with simple underlying graph) that is reflexible.
I will show how families of covers of graphs/maps can be used to prove that that for over 83\% of all positive integers g, there exists at least one orientably-regular map of genus g with simple underlying graph. This is joint work with my former PhD student Jicheng Ma. We conjecture that there exists at least one such map for every positive integer g.

Link to video showing pictures of regular maps, created by Jarke van Wijk (Eindhoven)
Presentation.


X
• Covering constructions of extremal graphs of given degree and diameter, or girth Jozef Siran, Slovak University of Technology, Bratislava, Slovak Republic

The degree-diameter problem is to determine the largest order of a graph \linebreak of a given maximum degree and diameter. The related problem of determination of the smallest order of a graph of a given degree and girth is sometimes called the degree-girth problem. In both cases our knowledge about the actual maxima/minima is rather limited. Nevertheless, there are a number of interesting bounds on these parameters obtained by constructions.
It turns out that a considerable proportion of the largest currently known graphs of given degree and diameter, and the smallest known graphs of given degree and girth, have been or can be obtained as lifts of small base graphs with voltages in groups with a fairly simple structure. In the talk we will give a survey of these constructions and outline open problems in this area of research.

Presentation.


X

Winter School Lectures

• Harmonic covers of graphs Alexander Mednykh, Novosibirsk State University, Russia

The aim of lectures is to give a background for the theory of graph coverings and harmonic maps.
The basic definitions and main results of the theory are followed by exercises. Some of these excises are elementary, some of them will require non-trivial effort and some of them are unsolved problems. Also, the basic theory will be provided by numerous examples and the most exercises by solutions.

Notes
Lecture_1_Laplacian Exercises_1_Laplacian Exercises_1_Solutions
Lecture_2_Spanning_trees Exercises_2_Spanning_trees Exercises_2_Solutions
Lecture_3_Graph_Coverings Exercises_3_Graph_Coverings
Lecture_4_Harmonic_maps Exercises_4_Harmonic_maps
Lecture_5_Jacobians

X
• Combinatorial Designs Alexander Rosa, McMaster University, Hamilton, Canada

Combinatorial design theory traces its origins to statistical theory of experimental design but also to recreational mathematics of the 19th century and to geometry. In the past forty years combinatorial design theory has developed into a vibrant independent branch of combinatorics with its own aims, methods and problems. It has found substantial applications in other branches of combinatorics, in graph theory, coding theory, theoretical computer science, statistics, and algebra, among others.
The objective of this short course is to convey a solid basic knowledge of problems and methods of combinatorial design theory, up to a level that will enable one to approach open research problems.

Notes

X

Registration & Fees

To register, please fill in the registration form here.
The registration fee covers conference admission and materials, accomodation and full board starting by Sunday dinner and ending by Friday lunch. Program begins Monday morning, therefore participants are expected to arrive on Sunday evening.

Fees for early registration - before December 20, 2013:

• 450 EUR for accommodation in a single room
• 350 EUR for accommodation in a double room
• 280 EUR for students (a double room, or a bungalow (= two double rooms & a living room, for 3-4-member groups)

For bank transfers use the following account informations. Transfers should be delivered by Jan 10, otherwise will be collected in chash at the workshop. Please make sure that the payment will be delivered free of all international transfer fees.

For late registration (on or after December 21, 2013) extra 50 EUR will be charged.

All the expenses will be covered for the members of the grant mobility project: "Mobility -- Enhancing Research, Science and Education" ITMS code: 26110230082, under the Operational Programme Education cofinanced by the European Social Fund.

We offer to cover the registration fee (including accomodation and board) for a limited number of PhD. students and postdocs interested to take part in the winter school courses. To get support it is necessary to register and write an extra e-mail to Roman Nedela (nedela at savbb.sk).

Accomodation & Travel Info

Address: Hotel Sepetna, Ostravice 0956, 739 14 Ostravice, Czech Republic.

Group transportation to and from the workshop will be offered from Prague.

Organizers