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
The conference photo.More photos on picasa.
ATCAGC Talks & ContributionsInvited talks:
- Rotary and regular maps with simple underlying graphs Marston Conder, University of Auckland, New Zealand
- Covering constructions of extremal graphs of given degree and diameter, or girth Jozef Siran, Slovak University of Technology, Bratislava, Slovak Republic
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.
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.
Winter School LecturesTopics and Speakers
- Harmonic covers of graphs Alexander Mednykh, Novosibirsk State University, Russia
- Combinatorial Designs Alexander Rosa, McMaster University, Hamilton, Canada
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.
Lecture_1_Laplacian Exercises_1_Laplacian Exercises_1_Solutions
Lecture_2_Spanning_trees Exercises_2_Spanning_trees Exercises_2_Solutions
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.
All Talks, Abstracts and Presentations
- List of Participants & Contributions
|Magdalena Adamska||AGH University of Science and Technology|
|Nino Bašić||University of Ljubljana|
|Marston Conder||University of Auckland||Rotary and regular maps with simple underlying graphs|
|Regular maps video by Jarke van Wijk (Eindhoven)|
|Eduard Eiben||FMFI UK|
|Jiri Fiala||Charles University||Locally constrained homomorphisms on graphs of bounded degree and bounded treewidth|
|Stefan Gyurki||Slovak University of Technology, Bratislava|
|Miroslav Haviar||Matej Bel University|
|Petr Hliněný||FI MU Brno||Computing the Stretch of an Embedded Graph|
|Katarína Hriňáková||Slovak University of Technology, Bratislava|
|Kan Hu||Matej Bel University||Almost totally branched coverings between regular hypermaps|
|Michal Ivaška||Matej Bel University|
|Robert Jajcay||FMFI UK|
|Ján Karabáš||Matej Bel University|
|Stanislav Kasaj||Matej Bel University|
|Pavel Klavik||Charles University in Prague||Algorithmic Aspects of Regular Graph Covers|
|Martin Knor||Slovak University of Technology in Bratislava||Domination in vertex-transitive cubic graphs on 2m vertices|
|Kristína Kováčiková||fmfi UK|
|Petr Kovář||VŠB Ostrava|
|Martin Macaj||Comenius University, Slovakia|
|Aleksander Malnic||University of Ljubljna and University of Primorska||On sectional split lifts|
|Alexander Mednykh||Sobolev Institute of Mathematics||On Wiman's theorem for graphs|
|Ilya Mednykh||Sobolev Institute of Mathematics||On isospectrality of genus two graph|
|Mariusz Meszka||AGH University of Science and Technology|
|Roman Nedela||Matej Bel University|
|Alexander Rosa||McMaster University|
|Michaela Seifrtová||Charles University|
|Adam Silber||VŠB-TU Ostrava|
|Jozef Širáň||Open University and Slovak Tech. Univ.||Covering constructions of extremal graphs of given degree and diameter, or girth|
|Marek Tesar||Charles University||On multi-covers and their applications|
|Katarína Tureková||Fmfi UK|
|Na-Er Wang||Matej Bel University||Regular embeddings of complete bipartite graphs with multiple edges|
|Maria Zdimalova||KMDG, SvF,STU, Bratislava||Construction of large digraphs of given degree and diameter and their symmetries|
|Peter Zeman||Charles University in Prague||Automorphism Groups of Geometrically Represented Graphs|
|Matan Ziv-Av||Ben-Gurion University of the Negev||Enumeration of S-rings over small groups|
|Alexandru Popa||Masaryk University|
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.
|IBAN||CZ22 0800 0000 0002 0003 0319|
|Bank address||Ceska sporitelna, pobocka Praha 8, Sokolovska 1, 186 53, Praha 8, Czech Republic|
|Account holder||Jednota ceskych matematiku a fyziku - CMS|
|Account number |
for domestic transfers
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.Hotel Sepetna is located at Beskydy mountains, on Czechoslovak border about 4 hours of drive/train from Pargue or Vienna.
Group transportation to and from the workshop will be offered from Prague.