Abstrakty 2023

13. července     Petr Kovář: Aplikace rozkladů grafů při paralelizaci numerických výpočtů hustých matic

V článku LUKÁŠ, D., KOVÁŘ, P., KOVÁŘOVÁ, T., MERTA, M., A parallel fast boundary element method using cyclic graph decompositions, z roku 2015 jsme navrhli metodu rozložení výpočtu husté matice na podmatice s využitím cyklického rozkladu kompletního grafu K_N na N kompletních podgrafů K_k. Parametry N a k cyklického rozkladu nejsou nezávislé, platí N = k²-k+1. Navíc existence cyklického rozkladu vychází z tzv. ρ-ohodnocení, jehož existence je známa pouze pro takové hodnoty parametru k, kde k-1 je mocninou prvočísla. Přístup pomocí cyklických rozkladů je omezen na systémy se sdílenou pamětí.

Vzhledem k vývoji architektury superpočítačů se rýsuje možnost implementace s využitím rychlých lokálních pamětí jednotlivých jader, avšak velikost lokální paměti je omezena. Má proto smysl studovat rozklady K_N na K_k, kde k jsou malé pevné hodnoty a N roste libovolně s počtem jader superpočítače. Takové rozklady nebudou cyklické, konstrukce vychází pro omezené parametry například ze Steinerovských systémů trojic či čtveřic a navíc pro další většinu hodnot N rozklady neexistují.

Na druhou stranu místo rozkladů lze s úspěchem využít pokrytí grafů, které vychází z konstrukcí kombinatorických designů. Část výpočtu na malém počtu jader je provedena duplicitně (respektive část paměti malého počtu jader se nevyužije). Duplicity lze modelovat zdvojenými hranami, kterým říkáme exces. Ukážeme, že pro většinu hodnot N je velikost excesu konstantní, jen pro málo hodnot N je násobkem N, a proto navržený model má smysl implementovat.

Pozvánka v PDF

 

13. července     Yifan Zhang: Covering of complete graphs by K₄

Covering a complete graph by quadruples leaves various types of excess depending on the order of the original graph. In this talk we discuss by case how to form the minimum covering out of classical combinatoric designs such as BIBD, GDD and PBDs. Certain exceptional cases, not present when covering by triangles, are also investigated, only to notice how insufficient the obviously necessary conditions are for a covering to exist.

Pozvánka v PDF

 

Abstrakty 2022

24. června     Tomáš Madaras: Homogeneous graph colorings

We introduce new kinds of graph colorings which can be described, using a unified framework, in the following way: Given a graph G and a list L = { H₁, ..., H_t} of (particular) subgraphs of G, a coloring c (vertex, edge, total etc.) of G is called homogeneous with respect to L if each subgraph from L sees the same number of colors. We present selected results on homogeneous colorings that are connected with subgraph lists consisting of open vertex neighborhoods, or vertex sets of faces (assumed that underlying graph is embedded to a surface), or else the maximal stars/double stars (for the edge coloring version). The relations to other coloring concepts (such as role colorings or M_q-colorings) are discussed as well.

V príspevku zavedieme nové druhy zafarbení grafov, ktoré možno pomocou jednotného rámca opísať nasledujúcim spôsobom: Pre daný graf G a zoznam L = { H₁, ..., H_t} (nejakých) podgrafov G, zafarbenie c (vrcholové, hranové, totálne atď.) $G$ sa nazýva homogénne vzhľadom na L, ak každý podgraf z L je zafarbený rovnakým počtom farieb. Prezentujeme vybrané výsledky o homogénnych zafarbeniach, ktoré sú indukované zoznamami podgrafov pozostávajúcich z otvorených okolí vrcholov alebo množín vrcholov stien (za predpokladu, že graf je vnorený do nejakej plochy resp. maximálnych hviezd/dvojhviezd (pre hranovú verziu zafarbenia). Diskutované tiež budú súvislosti s inými farebnými koncepciami (ako sú rolové zafarbenia resp. M_q-zafarbenia).

Pozvánka v PDF

 

24. června     Igor Fabrici: Unique-maximum colorings of plane graphs

(joint work with Simona Rindošová)

A proper vertex coloring of a plane graph is unique-maximum (UM) if, for every face, the maximum color on its vertices is used exactly once. Wendland (2016) proved that every plane graph is UM 5-vertex-colorable and Lidický, Messerschmidt, and Škrekovski (2018) constructed a plane graph with corresponding chromatic number 5.

In this talk, we consider following two modifications of the previous coloring:

1. a proper vertex-face coloring of a plane graph is unique-maximum (UM) if, for every face, the maximum color on its vertices and on the face itself is used exactly once,
2. a proper vertex coloring of a plane graph is unique-double-maximum (U2M) if, for every face, the highest color and the second highest color on its vertices are used exactly once,

we compare these two colorings, and prove that every plane graph is UM 8-vertex-face-colorable, UM 10-vertex-face-choosable, and U2M 9-vertex-colorable.

Pozvánka v PDF

 

24. června     Dalibor Fronček: Decomposition of complete graphs into unicyclic graphs with seven edges

(this is a joint work with Michael Kubesa)

An H-decomposition of a graph G is a collection of subgraphs H₁, H₂, ..., H_s of G, all isomorphic to H, such that every edge of G belongs to exactly one copy H_i. A unicyclic graph is a graph containing precisely one cycle.

The problem of decomposition of complete graphs has been completely solved for graphs with at most six edges, and with a few exceptions also for graphs with eight edges. However, for graphs with seven edges it was almost untouched except for trees. We therefore take the next natural step and examine decompositions into unicyclic graphs with seven edges.

The obvious necessary condition for such a decomposition into graphs with seven edges is that n≡0,1 (mod 7). We show that the condition is also sufficient for any connected unicyclic bipartite graph H with seven edges when n≡0 (mod 7) and n≡1 (mod 14) except for several cases when n=7 or 8. We may also show some partial results for the non-bipartite case.

For disconnected graphs, we present just partial results for the bipartite case, as the work is still in progress.

Pozvánka v PDF

 

26. května     Michael Kubesa: "Natahovací" labelingy jako postačující podmínka G-dekompozice kompletních grafů (dokončení)

Druhá část a dokončení přednášky.

Již od 60. let minulého století byly známy labelingy, které zajišťovaly, že graf G s hranami umožňuje G-dekompozici kompletních grafů K_2n+1, resp. K_2n. Některé, natahovací labelingy, dokonce umožňovaly G-dekompozici K_2kn+1, resp. K_2kn pro každé přirozené k. Ovšem tyto labelingy vyžadovaly, aby graf G s n hranami byl bipartitní. V této přednášce bychom chtěli prezentovat tripartitní ρ-labeling a 1-rotational tripartitní ρ-labeling, které umožňují G-dekompozici kompletních grafů K_2kn+1 a K_2kn i v případě, že G s n hranami není bipartitní, ale je tripartitní.

Pozvánka v PDF

 

3. května     Petr Kovář: Několik postřehů o rozkladech grafů II

Volně navážeme na předchozí přednášku. Budeme rozkládat kubické grafy na cesty P₄. Ukážeme, že takový rozklad existuje právě tehdy, když kubický graf má úplné párování.

Pozvánka v PDF

 

14. dubna     Petr Kovář: Několik postřehů o rozkladech grafů

Na semináři DiMaS se většinou věnujeme rozkladům kompletních grafů na izomorfní stromy. Chtěl bych upozornit na několik pěkných konstrukcí rozkladů různých grafů na cesty. Budeme rozkládat obecné grafy na cesty P₃ a kubické grafy na cesty P₄.

Pozvánka v PDF

 

22. března     Michael Kubesa: "Natahovací" labelingy jako postačující podmínka G-dekompozice kompletních grafů

Již od 60. let minulého století byly známy labelingy, které zajišťovaly, že graf G s hranami umožňuje G-dekompozici kompletních grafů K_2n+1, resp. K_2n. Některé, natahovací labelingy, dokonce umožňovaly G-dekompozici K_2kn+1, resp. K_2kn pro každé přirozené k. Ovšem tyto labelingy vyžadovaly, aby graf G s n hranami byl bipartitní. V této přednášce bychom chtěli prezentovat tripartitní ρ-labeling a 1-rotational tripartitní ρ-labeling, které umožňují G-dekompozici kompletních grafů K_2kn+1 a K_2kn i v případě, že G s n hranami není bipartitní, ale je tripartitní.

Pozvánka v PDF

 

Abstrakty 2021

5. listopadu     Riste Škrekovski: Some results on unique-maximum coloring of plane graphs

A unique-maximum coloring of a plane graph G is a proper vertex coloring by natural numbers such that each face α of G satisfies the propety: the maximal color that appears on α, appears precisely on one vertex of α (or shortly, the maximal color on a face is unique on that face). Fabrici and Göring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. Thus, the facial unique-maximum chromatic number of the sphere is not four but five. In the second part of the talk, we will consider various new directions and open problems.

Joint work with Vesna Andova, Bernard Lidický, Borut Lužar, and Kacy Messerschmidt

Pozvánka v PDF

 

5. listopadu     Borut Lužar: Edge-coloring subcubic graphs with five colors

A proper edge-coloring of a graph is an assignment of colors to its edges such that adjacent edges receive distinct colors. From Vizing's theorem it follows that every graph with maximum degree 3 admits a proper edge-coloring using at most 4 colors. It turns out that by allowing just one additional color (i.e., using 5 colors), we are able to add many interesting constraints to our edge-coloring setting and still be able to complete the coloring. In the talk, we will survey results about the most studied edge-coloring variations; we will begin with a recent result on the strong edge-coloring, and continue by considering normal and adjacent vertex-distinguishing edge-colorings. Although a considerable amount of research was done on the mentioned topics, there are still many interesting open problems waiting to be solved.

Pozvánka v PDF

 

5. listopadu     Kenny Štorgel: Further Extensions of the Grötzsch Theorem

The Grötzsch Theorem states that every triangle-free planar graph G admits a proper 3-coloring, i.e. a coloring of the vertices of G with three colors such that adjacent vertices are assigned distinct colors. However, we may also allow triangles in general planar graphs and still retain 3-colorability. Havel conjectured that a 3-colorable planar graph may contain arbitrarily many triangles as long as they are sufficiently far apart. This conjecture was proved by Dvořák, Kráľ, and Thomas. On the other hand, there are 3-colorable planar graphs that may have close triangles (even incident). A result by Dross et al. states that every planar graph obtained as a subgraph of the medial graph of a bipartite plane graph is 3-colorable.

As mentioned, the Grötzsch Theorem has many generalizations, although, perhaps the most well-known is a result of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, which is in general best possible. A lot of attention was also given to extending 3-colorings of subgraphs of triangle-free planar graphs to the whole graph. In particular, a result of Aksenov, Borodin, and Glebov states that we can precolor any two non-adjacent vertices in a triangle-free planar graph and retain 3-colorability. Furthermore, several other results exist which deal with precolorings of a face of certain length in a triangle-free planar graph.

In this talk, we will present the above-mentioned results and provide further extensions of the Grötzsch Theorem by considering 3-colorings of planar graphs with at most one triangle. In particular, we show that a precoloring of any two non-adjacent vertices and a precoloring of a face of length at most 4 can be extended to a 3-coloring of the whole graph. Additionally, we show that for every vertex of degree at most 3 in a planar graph with at most one triangle, a precoloring of its neighborhood with the same color extends to a 3-coloring of the whole graph. The latter result yields an affirmative answer to a conjecture on adynamic coloring.

This is a joint work with Hoang La and Borut Lužar.

Pozvánka v PDF

 

5. listopadu     Mirko Petruševski: Coverability by parity regular subgraphs

Only two types of graphs are `parity regular', that is, have all their vertex degrees of the same parity. Namely, these are the `even graphs' and the `odd graphs', where a graph is said to be even (resp. odd) if all its vertex degrees are even (resp. odd). An old result of Matthews from 1978 establishes a connection between nowhere-zero 2^k - flows in graphs and coverability by k even subgraphs, which in view of Jaeger's 8-flow and 4-flow theorems, respectively, implies that every bridgeless graph admits a cover by three even subgraphs and that every 4-edge-connected graph is coverable by two even subgraphs.

In this talk, we present some new results that complement the aforementioned. In particular, we characterize coverability by three odd subgraphs, and discuss coverability by every other possible combination of three parity regular subgraphs.

This is a joint work with Riste Škrekovski.

Pozvánka v PDF

 

13. července     Dalibor Froček: Γ-supermagic Labeling of Cartesian Products of Two Cycles

(joint work with Lincoln Sorensen and Peter Paananen)

A graph G=(V,E) with |V|=p, |E|=q is called Γ-supermagic if there exists a bijection f from E to an Abelian group Γ of order q such that the weight w(x) of each vertex x, defined as the sum of labels of all edges incident with x, is equal to the same magic element μ. In other words,

      w(x)=∑_{xy ∈ E} f(xy)=μ.

for all x ∈ V and some μ ∈ Γ. The labeling is called a Γ-supermagic labeling.

It was proved by DF, James McKeown, John McKeown, and Michael McKeown, that a Z_{2mn}-supermagic labeling of the Cartesian product C_m × C_n exists for all m, n ≥ 3.

We present some further results on Γ-supermagic labeling of C_m × C_n by other Abelian groups.

Keywords: Γ-supermagic labeling, group supermagic labeling

Pozvánka v PDF

 

25. června     Jakub Závada: On Scheduling of Incomplete Tournaments

Tournament in which n participants play each other in n-1 rounds is called a round robin tournament. This type of tournament is quite fair for each participant but for instance in lots of chess tournaments the number of participants is too large to play all n-1 rounds. So, how can we schedule a tournament with n participants into k, k < n-1 rounds if we want the tournament to be as fair as possible? Swiss system is often used but it cannot be used when we need to schedule the whole tournament ahead. We can try to use graph theory to find the best possible schedule.

Pozvánka v PDF

 

3. února     Róbert Jajcay: Algebraic constructions of cages

A cage with parameters (k,g) is a k-regular graph of girth g of the smallest possible order. Networks based on the use of cages often prove to be among the most efficient and reliable, and the search for cages (the Cage Problem) is an important part of Extremal Graph Theory as well as a widely studied optimization problem. Even though cages do not necessarily have to be algebraic objects, the majority of the known cages and of the smallest known (k,g)-graphs come from algebraic constructions. In our talk we will present a brief overview of the Cage Problem, describe some of the most successful algebraic constructions of small graphs of given degree and girth, and also address the question of the limitations of algebraic constructions.

Pozvánka v PDF

 

3. února     Tatiana Jajcayová: Partial automorphisms of graphs and algebraic tools to study them

The problem of determining the full automorphism group of a graph is one of the well-known hard problems. The focus of our recent joint project with Maria Szendrei, Nora Szakacs, and Robert Jajcay is on an extension of the automorphism group problem to that of inverse monoid problem. The full inverse monoid of partial automorphisms of a combinatorial structure is a much richer algebraical structure that contains more detailed local information about the underlying object. The goal is to apply the algebraic methods of partial permutation semigroup theory to the class of structures that admit none or only very few automorphisms and typically resist the use of methods from permutation group theory. The results involving partial automorphisms and use of inverse monoids may offer new insights into some well known and long open problems from Graph Theory, as we will illustrate with some examples.

A partial automorphism of a graph is an isomorphism between its induced subgraphs. The set of all partial automorphisms of a given structure forms an inverse monoid under composition of partial maps. In our presentation, we describe the algebraic structure of such inverse monoids by the means of the standard tools of inverse semigroup theory, and give a characterization of inverse monoids which arise as inverse monoids of partial graph (digraph and edge-colored digraph) automorphisms.

Pozvánka v PDF

 

3. února     Mária Mériová: Inverse monoids for certain classes of graphs

In order to better understand a specific combinatorial structure (for instance a graph) it is recommended to study, investigate and analyze the symmetries of this combinatorial structure. Up to recently, the main tools to study these symmetries were tools of Group Theory, that is full automorphisms and groups of full automorphisms. In cases where structures have no global symmetries and full automorphisms can not be used, these tools are rather limited. But the structures may still exhibit some local symmetries and thus their partial automorphisms are interesting.

Based on theoretical results published about local symmetries, we know that induced subgraphs need to be studied for graphs, and we have developed software that makes a list and analyzes the induced subgraphs of a given graph. Then, using these induced subgraphs, we studied the structure of inverse monoids related to the partial automorphisms of these graphs. At the beginning of our project, we have dealt with simple families of graphs: paths, cycles and trees, but we believe that our results can be generalized to other classes of graphs as well. As J. Nešetřil, M. Konečný et al. research suggests, another interesting class of graphs could be tournaments.

Pozvánka v PDF

 

3. února     Slobodan Filipovski: On bipartite cages of excess 4

The Moore bound M(k,g) is a lower bound on the order of k-regular graphs of girth g (denoted (k,g)-graphs). The excess e of a (k,g)-graph of order n is the difference n-M(k,g). In this talk we consider the existence of (k,g)-bipartite graphs of excess 4 via studying spectral properties of their adjacency matrices.

Pozvánka v PDF

 

3. února     Tom Raiman: Conditions for vertex removal in (k,g)-graphs

For almost sixty years there has been thorough research about properties of k,g)-graphs and (k,g)-cages. There have been a lot of attempts to improve lower and upper bounds for (k,g)-graphs given some qualities of these graphs. We want to show new ideas how to find smaller (k,g)-graphs from existing ones, while preserving the regularity and girth and show how these ideas may help to find new upper bounds that could be smaller than the existing ones.

Pozvánka v PDF

 

Abstrakty 2020

18. února     Tom Raiman: Conditions for vertex removal in (k,g)-graphs

A (k,g)-graph is graph with regularity k and girth g. Since 1960's it is known that (k,g)-graphs exists for every pair of k and g. Since then the goal is to find (k,g)-cages (cage is smallest possible (k,g)-graph). Although some cages had been found it very much unexplored territory. People try to at least improve currently best known lower bounds of so called records.

In this lecture we will look at the ways how people try to improve these records and how our methods differ from the currently know methods.

Pozvánka v PDF

 

30. ledna     Petr Kovář: Vertex in-out-antimagic total labeling of digraphs

This is a joint workjoint work with Martin Bača, Tereza Kovářová, and Andrea Semaničová-Feňovčíková

A vertex in-out-antimagic total labeling of a directed graph (digraph) D=(V,A) with n vertices and m arcs is a bijection from the set V ∪ A to the set of integers {1, 2, ..., m+n } such that all n vertex in-weights are pairwise distinct and simultaneously all n vertex out-weights are pairwise distinct, where the vertex in-weight is the sum of the vertex label and the labels of all incoming arcs and the vertex out-weight is the sum of the vertex label and the labels of all outgoing arcs.

In this talk we conjecture that all digraphs allow such labeling and provide a general way how to label dense digraphs and certain sparse digraphs.

Pozvánka v PDF

 

14. ledna     Ján Karabáš: Cycles and perfect matchings in snarks

The lecture is based on the results of the joint work with Roman Nedela and Martin Škoviera.

Every 3-edge-colourable cubic graph has a set of three perfect matchings that cover all of its edges. Conversely, if the edge set of a cubic graph can be covered with three perfect matchings, the matchings must be disjoint and the graph 3-edge-colourable. The cubic graphs not possesing any regular 3-edge-colourings are called snarks. It follows in snarks any collection of three perfect matchings misses some edges of a graph. The minimum number of edges of a cubic graph G left uncovered by any three perfect matchings will be called the colouring defect (shortly defect) of G and will be denoted by df(G). Clearly, a cubic graph has defect zero if and only if it is 3-edge-colourable and the number is grater than zero for snarks. This invariant has been introduced by E. Steffen in 2015 [3] and it appears to be interesting invariant of snarks.

We try to exhibit relationships of the defect of a snark to other invariants such as (colouring) resistance, oddness, girth, criticality, irreducibility [2] and others. It is quite easy to show that defect of snarks is greater or equal to three. Far the most of the snarks have defect equal to three, which implies a strong structural constraint – the existence of a six-cycle. We will show the smallest snark with defect greater than 3 and discuss the consequences of this observation. We will set the colouring defect for several families of snarks or, at least, we will present the working hypotheses on them. We will also exhibit the close relationship of the study of snarks with small defect and well-known hypotheses e.g. Berge-Fulkerson Conjecture and 6-decomposition theorem [1,2] (Jaeger Conjecture).

1. J. Karabáš, E. Máčajová, R. Nedela, 6-decomposition of snarks, European J. Combin. 34 (2013), 111–122.
2. R. Nedela and M. Škoviera, Decompositions and reductions of snarks, J. Graph Theory 22 (1996), 253–279
3. E. Steffen, 1-Factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015), 195–206

Pozvánka v PDF

 

Abstrakty 2019

1. listopadu     Petr Gregor: Symmetric chain decompositions and the central levels problem

A symmetric chain in the n-dimensional cube Q_n is a path of length n-2k that starts on level k and ends on level n-k for some k. Greene and Kleitman in 1970's described a decomposition of V(Q_n) into symmetric chains. The central levels problem asserts that the subgraph of the (2m+1)-dimensional cube induced by all vertices between levels m+1-l and m+l (i.e. the central 2l levels) has a Hamilton cycle for all m ≥ 1 and 1 ≤ l ≤ m+1. This problem raised by Savage is a common generalization of the well-known middle levels problem and classical binary Gray codes.

In the first part we give introduction to symmetric chain decompositions (SCDs) and Gray codes with their applications. In the second part we present a constructive solution to the central levels problem that is based on the Greene-Kleitman SCDs. In particular, we show that the Greene-Kleitman SCD extends to a Hamilton cycle of Q_n and there is a loopless algorithm to generate it. This is a joint work with Torsten Mütze and Ondřej Mička.

Pozvánka v PDF

 

10. září     Martin Škoviera: Point-line configurations in projective spaces and the structure of cubic graphs

We propose a unifying approach to several important conjectures in graph theory in terms of nowhere-zero flows on cubic graphs where flow-values are points of a configuration of lines in a projective space and outflow-patterns are triples of points sharing a line of the configuration. We then focus on the conjecture of Claude Berge suggesting that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. It turns out that cubic graphs that require five (or more) perfect matchings to cover their edges are extremely rare and hence difficult to find. We show that they can be efficiently studied by means of flows whose outflow patterns form a configuration of six lines spanned by four points of the 3-dimensional projective geometry PG(3,2) in general position. We employ this knowledge to provide a great variety of constructions of cubic graphs that cannot be covered with four perfect matchings. We finally show that one of our constructions provides counterexamples to a conjecture of Brinkmann et al. about the length of a shortest cycle cover of a cyclically 4- edge-connected cubic graph.

This is a joint work with Edita Máčajová.

Pozvánka v PDF

 

10. září     Edita Máčajová: Smallest counterexample to the Fulkerson conjecture must be cyclically 5-edge-connected

The Fulkerson conjecture belongs to one of the most prominent open problems in Graph theory. It suggests that the edges of any bridgeless cubic graph can be covered with six perfect matchings in such a way that each edge belongs to exactly two of them. The origin of this conjecture lies in mathematical programming and the conjecture itself has close connections to configurations of points and lines in the projective space. Despite the fact that Berge and Fulkerson made this conjecture almost half a century ago, it has been verified only for several explicitly defined families of graphs. During the talk we will present the current state of this conjecture as well as its connections to other important conjectures in graph theory. As the main result we show that Fulkerson’s conjecture can be reduced to cyclically 5-edge-connected cubic graphs.

This is a joint work with Giuseppe Mazzuoccolo.

Pozvánka v PDF

 

10. září     Tom Raiman: Use of generalized truncation for computer search for (k,g)-graphs

A (k,g)-graph is a graph with regularity k and girth g. We investigate the use of generalized truncation in improving the upper bound of (k,6) and (k,8)-bound, where k=q+2 and q a is prime power. We also discuss conditions under which one can reverse generalized truncation. We have done this with the aim of obtaining a tool for proving the existence or non-existence of the (57,5)-Moore graph.

Pozvánka v PDF

 

10. září     Petr Kovář: Supermagic graphs with arbitrary degree differences

We present a recent result on constructing supermagic graphs. Given given an arbitrary nondecreasing sequence of nonnegative integers a₁, a₂, ..., a_n-1 there exists supermagic graph with degrees from the list d₁, d₂, ..., d_n, such that a_i = d_i+1-d_i for all i = 1, 2, ..., n-1.

Pozvánka v PDF

 

Abstrakty 2019

20. srpna     Dalibor Froček: Supermagic graphs with many different degrees

(joint work with Petr Kovář)

A graph G=(V,E) is called supermagic if there exists a bijection f: E → {1, 2, ..., |E|} called supermagic labeling such the weight of every vertex x ∈ V defined as the sum of labels f(xy) of all edges xy incident with x is equal to the same number m, called the supermagic constant. That is,

∃ m ∈ N ∀ x ∈ V: w(x) = ∑_{xy ∈ E} f(xy) = m.

Typically, the classes of graphs studied in this context are vertex-regular or even vertex-transitive. Recently, Kovář et al. affirmatively answered a question by Madaras:

Does there exist a supermagic graph with k different degrees for any positive integer k?

Because their construction provided only graphs where all degrees were even, they asked the following more specific question:

Does there exist a supermagic graph with k different odd degrees for any positive integer k?

We answer this question in the affirmative by providing a construction based on the use of 3-dimensional magic rectangles.

The obvious next step is to ask the following:

Let k>1 be an integer and s_1, s_2, ..., s_{k-1} a sequence of positive integers. Is there a positive integer a_1 such that there exists a supermagic graph with degrees a_1, a_2, ..., a_k where a_{i+1}=a_i+s_i for i=1, 2, ..., k-1?

We also present a sketch of two proposed constructions of graphs hopefully answering the above question in the affirmative.

Keywords: Supermagic graphs, magic-type labeling, edge labeling

Pozvánka v PDF

 

2. listopadu     Petr Kovář: Highly irregular supermagic graphs

(joint work with Michal Kravčenko, Matěj Krbeček, and Adam Silber)

Let G = (V, E) be a graph with m edges. A bijection f : F → { a, a+1, ..., a+m-1 } for some integer a is called a supermagic labeling of G if for every vertex v the sum of edge-labels of all edges adjacent to v is equal to the same integer k. The constant k is the \emph{magic constant} of f and any graph which admits a supermagic labeling is a supermagic graph. The concept of magic graphs (with arbitrary real labels) is one on the oldest labeling concepts. It originated by Sedláček in 1963. Supermagic labelings were introduced by Stewart in 1967.

Dozens of papers have been published on supermagic labelings, mostly providing constructions of supermagic labelings of a specific class of graphs as well as some necessary conditions for the graph to allow a supermagic labeling. The proofs are mostly constructive, usually providing a labeling technique for regular or almost regular graphs. Some supermagic graphs with different degrees were provided by Ivančo and Semaničová in 2005 or Ivančo and Polláková in 2012 and 2014. Recently we obtained a general construction of supermagic graphs with arbitrarily many different degrees. Today we present the result as well as some open problems this area.

Pozvánka v PDF

 

1. června     Dalibor Fronček: How close to being platonic can you get?

(joint work with Jiangyi Qiu)

A Platonic graph is a vertex-regular planar graph with all faces of the same size. It is well known that there exist exactly five such graphs: tetrahedron, octahedron, hexahedron, icosahedron, and dodecahedron. Recently, William Keith asked whether there exist nearly Platonic graphs that would differ from Platonic in just one face. That is, vertex-regular planar graphs with all faces except one having the same size. W. Keith, D. Kreher and the speaker then showed (or at least believed that they had shown) that no such graphs exist [1]. On the other hand, there are well known classes of 2-nearly Platonic graphs with exactly two exceptional faces, both of the same size. We will and ask (and partially answer) some questions about 2- and 3-nearly Platonic graphs. In other words, about vertex-regular planar graphs with exactly two or three exceptional faces.

[1] W. Keith, D. Froncek, D. Kreher, A note on nearly Platonic graphs, Australas. J. Combin. (2017), 86-103.

Pozvánka v PDF

 

5. května     Tom Raiman: Conditions for adding vertices to (k,g)-graphs

A (k,g)-graph is a k-regular graph of girth g. A (k,g)-graph of the smallest possible order is called a (k,g)-cage. The Cage Problem is the problem of finding such smallest graphs and their orders for all pairs k,g ≥ 3. This problem has been extensively studied since the 1960's when Erdös and Sachs proved the existence of infinitely many (k,g)-graphs for any pair (k,g). Their original upper bound on the order of cages has been later improved by Sauer. In each case, an order was found with the property that a (k,g)-graph exists for each admissible order larger than this bound. We present a different approach and study the properties of (k,g)-graphs that can be extended into larger (k,g)-graphs by adding vertices. This approach may potentially give rise to recursive constructions based on smaller graphs than those identified by Erdös, Sachs, and Sauer.

Pozvánka v PDF

 

Abstrakty 2017

8. listopadu     Dalibor Fronček: Some cycle products are more magic than others

A Cartesian product CmCn of two cycles Cm and Cn can be seen as a toroidal m × n grid with mn vertices of degree four and 2mn edges. We can bijectively label the edges, vertices, or both by consecutive positive integers 1, 2, . . . , s or by elements of an Abelian group Γ of order (where s is the number of labeled elements) and define the weight of an element (that is, an edge or a vertex) as the sum of labels of the adjacent and/or incident elements. When the weights of all elements in question are equal, we call the labeling magic (of some kind). When the weights are all different, the labeling is called antimagic. I will present some old and new results on various kinds of magic labelings of cycle products and pose several open questions. The results are based on collaboration with several co-authors, including Tereza Kovářová, Petr Kovář, Jack McKeown, James McKeown, Michael McKeown, and Yichen Wei.

Pozvánka v PDF

 

23. října     Michael Kubesa: Faktorizace kompletních grafů na kostry

Kostra grafu je souvislý faktor grafu G, který neobsahuje cykly. Nejdříve se seznámíme s pojmem semisurjektivní a bicyklická faktorizace kompletního grafu, uvedeme jednoduché nutné podmínky pro faktorizace z názvu přednášky. Pak objasníme pojmy symetrický ρ-labeling, blended labeling a swapping labeling, což jsou postačující podmínky pro semisurjektivní faktorizace kompletních grafů na kostry.

TATO PŘEDNÁŠKA je 2. PŘEDNÁŠKA trojpřednáškového cyklu a je určena doktorandům a výzkumníkům, kteří se zabývají problémy diskrétní matematiky.

Pozvánka v PDF

 

9. října     Michael Kubesa: Základy dekompozic a faktorizací kompletních a kompletních bipartitních grafů

Řekneme si, co je dekompozice a faktorizace grafů. Dále se zaměříme na postačující podmínky dekompozice a faktorizace kompletních a kompletních bipartitních grafů, které uvedeme ve formě tzv. labelingu. Budeme hovořit o graceful labelingu, ρ-labelingu a bipartitním ρ-labelingu. Budeme tedy hovořit jen o nejzákladnějších labelinzích týkajících se dekompozic a faktorizací. Kdo by se o nich chtěl dovědět více, doporučujeme: Joseph A. Gallian, A Dynamic Survey of Graph Labeling.

TATO PŘEDNÁŠKA je 1. PŘEDNÁŠKA trojpřednáškového cyklu a je určena především doktorandům, kteří se v rámci postgraduálního studia zabývají problémy diskrétní matematiky.

Pozvánka v PDF

 

3. října     Štefan Gyürki: Directed strongly regular graphs

Since the main objects of interest in algebraic graph theory are highly symmetric graphs, strongly regular graphs are playing a central role in this area. One of their possible generalization for directed graphs was given by Duval in 1988. A directed strongly regular graph (DSRG) with parameters (n, k, t, λ, μ) is a regular directed graph on vertices with valency k such that every vertex is incident with t undirected edges; the number of directed paths of length 2 directed from a vertex x to another vertex y is λ, if there is an arc from x to y and μ otherwise. In this talk we mention their basic properties and several constructions of such graphs

Pozvánka v PDF

 

27. června     Tom Raiman: Grafy geometrických designů (2)-([2⁸,3,21])

(t)-([q^n,k,λ]) design na (n)-dimenzionálním vektorovém prostoru stupně (q) je množina (B) (k)-dimenzionálních podprostorů ((k)-podprostory), nazývané bloky, takové, že libovolný (t)-dimenzionální podprostor ((t)-podprostor) je podprostorem přesně (λ) bloků. Takový design označujeme jako ((V,B)). Je-li (t)-podprostor podprostorem (k)-podprostoru jsou tyto podprostory incidentní. Graf poté vyjadřuje incidenci mezi (k)- a (t)-podprostorem. Zaměříme se na grafy, které vzniknou z designu (2)-([2⁸,3,21]).

Pozvánka v PDF

 

12. ledna     Dalibor Fronček: Decompositions of complete bipartite graphs into prisms revisited

A generalized prism, or more specifically an (0,j)-prism of order 2n (where n is even) is a cubic graph consisting of two cycles u₀, u₁, ..., u_n-1 and v₀, v₁, ..., v_n-1 joined by two sets of spokes, namely u₁v₁, u₃v₃, ..., u_n-1v_n-1 and u₀v_j, u₂v_j+2, ..., u_n-2v_j-2. The question of factorization of complete bipartite graphs into (0,j)-prisms was completely settled by the author and S. Cichacz. Some partial results on decompositions of complete bipartite graphs have also been obtained by S. Cichacz, DF, and P. Kovar, and on decompositions of complete graphs S. Cichacz, S. Dib, and DF. The problem of decomposition of complete graphs into prisms of order 12 and 16 was completely solved by S. Cichacz, DF and M. Meszka. In June 2014 I presented what I had believed was a complete solution for the decomposition of complete bipartite graphs into (0,0)-prisms (that is, the usual prisms). In the same talk I mentioned my presentation in March 2014 in Boca Raton, Florida, where I had to admit that the results I had promised in my abstract were not covering any new cases, but rather just re-proved previously known results. This time, I will retract what I have retracted, and order what I have ordered.

Pozvánka v PDF

 

Abstrakty 2016

12. prosince     Robert Jajcay: Counting cycles in graphs with small excess

A (k,g)-cage is a k-regular graph of girth g that has the smallest number of vertices among all graphs with the parameters k and g. The orders of cages are bounded from below by the well-known Moore bounds, however, the exact orders are not known for the majority of cages. The excess of a cage is the difference between its order and the Moore bound, and a systematic study of the excesses of cages leads to improved lower bounds on their orders. We present some of the most recent improvements based on counting cycles.

Pozvánka v PDF

 

20. dubna     Wilfried Imrich: Symmetry breaking in graphs

In a graph, a set of vertices that is stabilized setwise by only the trivial automorphism is called a distinguishing set. Tom Tucker conjectured that every connected, infinite locally finite graph G has such a set if each nontrivial automorphism of G moves infinitely many vertices. The conjecture is know as the Infinite Motion Conjecture. It is still open despite the fact that numerous large classes of graphs have been shown to satisfy it.

In finite graphs distinguishing sets, if they exist, can be very small in comparison to the size of the graph, and in infinite graphs such sets can be finite. If they are not finite, their density can be zero. This talk presents classes of graphs that have distinguishing sets of zero density. Moreover, it is shown that the Infinite Motion Conjecture is true for cubic graphs.

Pozvánka v PDF

 

12. dubna     Tom Raiman: Faktorizace grafů na pulce

Faktorizace kompletních grafů představuje klasický problém nejen z teorie grafů, ale i teorie designů. Toto téma je zkoumáno od 60. let 20. století. Co se týče faktorizace kompletních grafů byly známy pouze zřejmé výsledky (faktorizace na hamiltonovské cesty a dvojhvězdy). V poslední době byly nalezeny třídy koster, které faktorizují a které ne. Mezi ně patří některé housenky a langusty. Momentálně jsou zkoumány faktorizace kompletních grafů na unicyklické grafy zvané pulci. Unicykly lze faktorizovat pouze kompletní grafy s lichým počtem vrcholů, tzn. K_2n+1. Pro faktorizace kompletních grafů na pulce používáme modifikované metody faktorizací kompletních grafů na kostry. Zejména smíšené ohodnocení pro n liché a přepínací ohodnocení pro n sudé. Nyní je výzkum veden pro n liché, protože smíšené ohodnocení je jednodušší.

Pozvánka v PDF

 

25. ledna     Tomáš Gavenčiak: Hry na grafech

Seznámení s hrami na četníky a lupiče zaměřené na geometrické grafy (jako jsou třeba rovinné, intervalové či křivkové) a se zajímavými výsledky poslední doby.

Hry na četníky a lupiče mají mnohem blíže k abstraktním deskovým hrám a (snad trochu překvapivě) k strukturální a výpočetní složitosti, než k aplikované bezpečnosti, a jsou elegantní kapitolou (už tak hravé) teorie kombinatorických her.

Pozvánka v PDF

 

5. ledna     Dalibor Fronček: Group distance magic labelings of hypercubes and Cartesian products of cycles

Let G be a graph with n vertices and f a bijection f:V(G) -> {1,2,...,n}. We define the weight of vertex x as the sum of the labels of its neighbors, that is, w(x)=∑_{xy∈E(G)}f(y).

When all vertices have the same weight, say w(x)=m for every x, then f is called distance magic labeling and G is a distance magic graph.

However, it turns out that this type of magic labeling is very restrictive and consequently even many classes of vertex transitive graphs are not distance magic.

As an example, we prove that for d≡0,1,3 mod 4 the hypercube Q_d with 2^d vertices is not distance magic. On the other hand, we disprove a conjecture by Acharya, Rao, Singh and Parameswaran, who believed that hypercubes are not distance magic except Q_2 and present a distance magic labeling for Q_6. This was recently generalized by Gregor and Kovar who found a distance magic labeling for of Q_d for any d≡2 mod 4.

Such negative results then rise a question whether it would not be more natural to perform the addition in Z_n rather than in Z. Graphs that satisfy the above definition with the provision that the addition is performed in Z_n will be called Z_n-distance magic.

To support this idea, we show some examples of graphs that are not distance magic yet are Z_n-distance magic. We show that when we perform addition Z_{2^d} rather than in Z, then Q_d is Z_{2^d}-distance magic if and only if d is even.

We present some results on Γ-distance magic labelings of products of cycles and pose several open problems.

Pozvánka v PDF

 

Abstrakty 2014

6. listopadu     Kateřina Volná, Matěj Krbeček: Arboricita, Orientace planárního grafu

První část semináře bude věnována arboricitě grafu. Kateřina Volná zavede pojem arboricity, neboli stromovitosti, kterou lze využít při hledání nejmenšího odchozího stupně vrcholu v grafu. Uvede jednotlivé druhy arboricity a také souvislost s chromatickým číslem grafu. Závěr prezentace je pak věnován algoritmům a jejich složitosti.

Druhá část seminář bude o 3-bounded orientaci v planárním grafu. Matěj Krbeček se bude věnovat problematice d-bounded orientace, konkrétně 3-bounded a jejímu nalezení v planárních grafech. Nadefinujeme základní pojmy a zmíníme věty týkající se dané problematiky. Popíšeme si algoritmus s lineární složitostí, který využívá tzv. reducibilních vrcholů.

Pozvánka v PDF

 

30. října     Jiří Fiala: Hledání Hamiltonovských cest v intervalových grafech

V přednášce se budeme zabývat problémem, zdali lze množinu reálných intervalů uspořádat do posloupnosti tak, že každé dva po sobě následující intervaly mají neprázdný průnik. Pro tento problém bude představen algoritmus a s jeho pomocí se ukáže, že jistá zřejmá nutná podmínka pro existenci takového uspořádání je zároveň i postačující.

Jinými slovy, buď daná posloupnost existuje, pak ji lze nalézt a ověřit patřičné vlastnosti; nebo neexistuje a i v tomto případě lze relativně snadno nalézt argument proč ani existovat nemůže. To je jeden z mála případů, kdy má obecně výpočetně těžký problém stručné důkazy pro případy kladných i záporných odpovědí.

Přednáška je určená široké veřejnosti, žádné odborné znalosti z kombinatoriky ani výpočetní složitosti nejsou nutné k porozumění tématu.

Pozvánka v PDF

 

20. června     Dalibor Fronček: Decompositions of complete bipartite graphs into prisms

A generalized prism, or more specifically an (0,j)-prism of order 2n (where n is even) is a cubic graph consisting of two cycles u_0,u_1,...,u_{n-1} and v_0,v_1,..,v_{n-1} joined by two sets of spokes, namely u_1 v_1, u_3 v_3,...,u_{n-1}v_{n-1} and u_0 v_j, u_2 v_{j+2},...,u_{n-2}v_{j-2}.

The question of factorization of complete bipartite graphs into (0,j)-prisms was completely settled by the author and S. Cichacz. Some partial results on decompositions of complete bipartite graphs and complete graphs have also been obtained by them and P. Kovar and S. Dib, respectively. The problem of decomposition of complete graphs into prisms of order 12 and 16 was completely solved by the author with S. Cichacz and M. Meszka and presented at IWONT 2012.

We will present a complete solution for the decomposition of complete bipartite graphs into (0,0)-prisms (that is, the usual prisms).

Pozvánka v PDF

 

2. června     Michael Kubesa: 15 školaček podruhé, Kirkmanovy trojúhelníkové systémy (KTS) vyšších řádů

V první přednášce bude dokončen výklad k rho- a bipartitnímu rho-ohodnocení. Dále bude vyřešen problém 15 školaček pomocí faktorizace kompletního grafu. Ukážeme, že touto metodou jsme schopni vytvořit KTS(15). Ve druhé části bude předvedena rekurzivní konstrukce KTS(6n+3), je-li n větší než 2.

Pozvánka v PDF

 

26. května     Michael Kubesa: Problém 15 školaček aneb Kirkmanovy trojúhelníkové systémy (KTS)

15 školaček v internátní škole se má procházet každý den po trojicích v pěti řadách. Naplánujte jejich rozdělení do trojic na každý den v týdnu (7 dnů) tak, že každá dvojice se v rámci trojic potká právě jednou. Ukážeme si řešení tohoto úkolu, přičemž ozřejmíme souvislost mezi tvorbou seskupitelných designů a faktorizací kompletních grafů. Čili si ukážeme konstrukci KTS pro 9 a 15 prvků. Konstrukce KTS vyšších řádů budou uvedeny v další přednášce.

Pozvánka v PDF

 

21. května     Tereza Kovářová, Kateřina Volná: Teorie designů (část 4)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. Ve čtvrtém z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, si ukážeme konstrukce Balanced Tournament Designu v souvislosti s aplikací tohoto designu při vytváření rozpisu turnaje s speciálním požadavkem na umístění zápasů.

Pozvánka v PDF

 

25. dubna     Petr Kovář: Teorie designů (část 3)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. Ve třetím z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, se budeme věnovat konstrukcím Steinerovských systémů trojic.

Pozvánka v PDF

 

24. dubna     Róbert Jajcay: Symmetric cages (Symetrické klietky)

A (k,g)-cage is a smallest k-regular graph of girth g. Finding a (k,g)-cage for given parameters k and g is thus an optimization problem in which one looks for an extremal graph in an infinite search space of all k-regular graphs of girth g. The search for cages started in earnest in the 1960's, but turned out to be too hard in general, and has only recently been revived due to the introduction of algebraic and topological methods in the area. In our talk, we present an overview of the contributions stemming of the use of Cayley and vertex-transitive graphs as well as some recent results concerning the restriction of the original cage problem to these two classes of symmetric graphs. The talk is aimed at general mathematical audience including students.

Pozvánka v PDF

 

11. dubna     Petr Kovář: Teorie designů (část 2)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. V druhém z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, se budeme věnovat Steinerovským systémům trojic.

Pozvánka v PDF

 

4. dubna     Petr Kovář: Teorie designů (část 1)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. V prvním z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, zavedeme základní pojmy a zformulujeme hlavní problém teorie designů.

Pozvánka v PDF

 

13. ledna     Tereza Kovářová: Handicapové grafy vyšších pravidelností

(spoluautor Petr Kovář)

Handicapové ohodnocení grafů má potenciál při sestavování neúplných turnajů ve kterých součet sil protihráčů každého týmu je tím větší čím silnější tým je. Na semináři byly dříve prezentovány výsledky týkající se konstrukcí handicapových ohodnocení 3-pravidelných a 5-pravidelných grafů. Jedním z nevyřešených problémů bylo nalezení handicapového ohodnocení pro grafy s vyšší pravidelností. V této navazující přednášce budou ukázány možnosti konstrukcí tohoto ohodnocení r-pravidelných grafů na n vrcholech, pro všechna přípustná r < n-10.

Pozvánka v PDF

 

Abstrakty 2013

13. prosince     Michael Kubesa: Orientace rovinných grafů

Chceme orientovat jednoduchý konečný rovinný graf tak, aby největší odchozí stupeň grafu byl co nejmenší. Tento problém souvisí s vhodnou paralelizací výpočtu v numerických úlohách.

Pozvánka v PDF

 

6. prosince     Pavla Hrušková: Několik vybraných aplikací spektrální teorie grafů

V úvodu přednášky se seznámíme s pojmem spektrum grafu. Spektrem grafu je myšlena množina vlastních čísel a vlastních vektorů grafu, který pro tyto účely reprezentujeme maticí. Jako vhodná maticová reprezentace se pro tyto účely používá nejčastěji matice sousednosti, případně Laplaceova matice. Ukážeme známá spektra některých vybraných typů grafů, konkrétně cesty a kartézského produktu dvou cest, což v numerické matematice odpovídá 1D, resp. 2D čtvercové síti.

V další části připomeneme aplikaci na využití spektra grafů pro důkaz neexistence faktorizace kompletního grafu pomocí 3 Petersenových grafů, pro který ale potřebujeme znalost kompletního spektra a dále se budeme zabývat aplikacemi využívající pouze část spektra (zpravidla vlastní vektory odpovídající několika největším, resp. nejmenším, vlastním číslům).

Nejdříve ukážeme nejběžnější použití vlastních vektorů Lapaceovy matice na spektrální dělení grafů poprvé zmíněné již Prof. Fiedlerem v 70. letech (první aplikace pochází z 80.-90.let). Dále ukážeme použití vlastních vektorů Laplaceovy matice pro nalezení optimální volby tzv. fixujících vrcholů používaných při řešení některých typů numerických úloh pomocí FETI metod, konkrétně úloh se semidefinitní maticí tuhosti. Obdobné myšlenky se uplatňují v obecných aplikacích typu (spektrální) kreslení grafů případně clusterování grafů. Jedna z nejznámnějších aplikací spektrální teorie grafů je Google ranking algoritmus používaný ve vyhledávacím enginu Googlu. Mnohé z těchto aplikací se v dnešní době s úspěchem používají také v různých sociálních sítích (clustering, eigenvector centrality apod.).

Pozvánka v PDF

 

26. listopadu     Tereza Kovářová: Postupy diskrétní matematiky při losování reálné sportovní soutěže

(spoluautorka Kateřina Volná)

Pro plánování amatérské soutěže ve sportovní střelbě, kdy se na různých střeleckých drahách utkají vždy dvojice střelců, je nutno uvážit:

• počet účastníků soutěže,
• omezení počtu střeleckých drah,
• dostatečné, avšak nepříliš dlouhé přestávky mezi jednotlivými koly pro každého hráče,
• pravidelné střídání drah a na každé dráze střídání pozice vlevo či vpravo.

V rámci přednášky bude ukázáno, jak lze pro sestavení rozpisu s výhodou využít nástrojů diskrétní matematiky, jako jsou rozklady kompletních grafů nebo latinské čtverce a další.

Pozvánka v PDF

 

22. listoadu     Michael Kubesa: Neplanarita grafu, Toky v sítích

Seminář bude didakticky zaměřen. Bude prodiskutováno použití Kuratowského věty k zjištění neplanarity grafu, užití Ford Fulkersonova algoritmu k vyhledání největšího toku a nejmenšího řezu v síti.

Pozvánka v PDF

 

8. listoadu     Petr Kovář: Hranová barvení grafů

Při paralelizaci numerického výpočtu vyvstala úloha, kterou je možno zformulovat v řeči teorie grafů: máme různě ohodnocené vrcholy a hledáme takové hranové ohodnocení, kdy hodnota přiřazená každé hraně odpovídá hodnotě jednoho koncového vrcholu. Ukážeme teoretické ohraničení počtu barev (myšlenku existenčního důkazu). Na tomto pracovním semináři uvedeme problém hledání konstruktivního důkazu, který by bylo možno použít pro rychlé nalezení takového ohodnocení.

Pozvánka v PDF

 

29. října     Michael Kubesa: Princip inkluze, exkluze a jeho nevhodné použití

V přednášce si ukážeme chybné použití principu inkluze a exkluze, chybu identifikujeme, rozebereme a ukážeme správné řešení.

Pozvánka v PDF

 

2. května     Pavla Kabelíková: Využití spektrálních vlastností grafů pro ověření (ne)existence faktorizací

Faktorizace grafu H na množinu hranově disjunktních navzájem izomorfních podgrafů G_1, G_2, ..., G_k je takový rozklad grafu H, kdy každá hrana grafu H patří do právě jednoho podgrafu G_i, každý podgraf G_i obsahuje všechny vrcholy původního grafu H a žádný vrchol není izolovaný. Problém nalezení faktorizace grafu na podgrafy je předpokládán za NP-úplný a pro některé třídy grafů je jeho NP-úplnost dokázána. K nalezení faktorizací některých tříd grafů se využívá různých grafových technik.

Vzhledem k tomu, že jsou podgrafy G_i izomorfní, jsou jejich matice podobné (ve smyslu algebraické podobnosti matic) a mají tedy stejné spektrum. K výpočtu spektra matic může být využita nějaká iterační metoda. V tomto pracovním semináři nejprve ukážeme s využitím znalosti spektra jednotlivých grafů, že kompletní graf na 10 vrcholech nemůže být faktorizován třemi Petersenovými grafy. Tento známý výsledek využivá velmi specifické struktury spektra Petersenova grafu a jeho vztahu ke spektru kompletního grafu. Cílem semináře bude pokus o aplikování této nebo obdobné konstrukce i na jiné typy grafů.

Pozvánka v PDF, prezentace v PDF, fotky

 

18. dubna     Přemysl Holub: Duhově souvislé grafy

Mějme dán hranově obarvený graf G. Řekneme, že G je duhově souvislý, jestliže každé dva vrcholy grafu jsou spojeny duhovou cestou (všechny hrany cesty mají rozdílné barvy). Nejmenší počet barev k potřebný k obarvení hran grafu G tak, aby G byl duhově souvislý, nazveme duhovou souvislostí grafu. Cílem přednášky bude seznámení se s tímto pojmem a některými známými výsledky z této oblasti.

Pozvánka v PDF. Prezentace v PDF.

 

28. března     Petr Kovář, Martin Kovář: Magická ohodnocení - otevřené problémy

Za posledního čtvrt roku se podařilo dotáhnout do konce důkazy některých výsledků, ale současně vyvstaly nové zajímavé otázky. Na ty nejzajímavější z nich upozorníme.

Pozvánka v PDF.

 

Abstrakty 2012

10. prosince     Pavel Jahoda: Množiny dokonalých rozdílů

Přednáška bude pojednávati o tom, kterak nalézti množinu dokonalých rozdílů (perfect difference set).

Pozvánka v PDF.

 

4. prosince     Pavel Jahoda: Co je konečné těleso?

Co je to těleso? Co je konečné těleso? Existují vůbec? Kolik může mít prvků? Jak nějaké zkonstruovat? Proč by měl být polynom použitý při konstrukci konečného tělesa ireducibilní? Dostanu pro různé ireducibilní polynomy při konstrukci konečného tělesa různá konečná tělesa? Kolik různých těles s daným počtem prvků existuje? Trápí Vás alespoň jedna z těchto otázek? Přijďte!

Pozvánka v PDF.

 

27. listopadu     Petr Kovář: Využití rozkladů grafů na husté podgrafy při paralelní implementaci BEM

spoluautoři: D. Lukáš, T. Kovářová a M. Kravčenko

Naším úkolem bude rozdělit n² bloků B_ij rozsáhlé matice do n skupin tak, aby v každé skupině byly bloky s co nejmenším počtem různých indexů. Ukážeme jaká jsou teoretická omezení pro tento minimální počet indexů při pevně zvoleném počtu n a ukážeme, že pro nekonečně mnoho různých hodnot umíme tohoto optima dosáhnout. Důkaz je konstruktivní, vychází z rozkladů kompletních grafů na husté podgrafy a umožní pro vybrané hodnoty n optimálně implementovat úlohu z minulé přednášky. Na závěr zmíníme několik zobecnění, která umožní dosáhnout počtu různých indexů blízkých optimální hodnotě i pro další hodnoty n, pro které neexistuje optimální řešení.

Pozvánka v PDF.

 

19. listopadu     Dalibor Lukáš: Paralelní metoda hraničních prvků pomocí cyklické dekompozice grafů

spolu s P. Kovářem, T. Kovářovou, M. Mertou a M. Kravčenkem

Metoda hraničních prvků je numerická metoda pro řešení okrajových úloh některých parciálních diferenciální rovnic. Metoda vede na soustavu lineárních rovnic s plnou maticí, jejíž řádky i sloupce odpovídají prvkům triangulace 3d výpočetní oblasti. Při paralelním sestavení řídké aproximace této matice chceme distribuovat triangulaci tak, aby výpočet spotřeboval minimum času i paměti. Ukazuje se, že pro jisté počty procesorů taková optima dostaneme pomocí cyklické dekompozice úplných grafů.

V přednášce pro ilustraci odvodíme hraniční formulaci Dirichletovy úlohy pro Laplaceovu rovnici v 1 dimenzi. Pro analogickou úlohu ve více dimenzích napíšeme vzorce pro výpočet prvků plné matice a popíšeme její řídkou aproximaci. Konečně formulujeme požadavky na její optimální paralelizaci a ukážeme, že některá optima máme díky cyklické dekompozici grafů.

Pozvánka v PDF.

 

12. listopadu     Michael Kubesa: T-faktorizace kompletních grafů

Mějme podgrafy G_1,G_2,...,G_s, kompletního grafu, které jsou všechny izomorfní s grafem G. Patří-li každá hrana kompletního grafu do přesně jednoho podgrafu G_i, pak jde o G-dekompozici kompletního grafu. Obsahují-li podgrafy G_i všechny vrcholy kompletního grafu a žádný vrchol není v G_i izolovaný, pak G-dekompozici nazýváme G-faktorizací. My se v přednášce zaměříme na G-faktorizace, kdy G je strom (souvislý graf bez cyklů). Protože G je strom, označíme jej T. V T-faktorizaci kompletního grafu je tedy každý podgraf T_i stromem a obsahuje všechny vrcholy kompletního grafu, Takovým podgrafům budeme říkat kostry kompletního grafu. Snadno lze ukázat, že T-faktorizaci lze provést pouze pro kompletní grafy se sudým počtem vrcholů, a že v T nesmí být žádnývrchol vyššího stupně než-li n, má-li kompletní graf 2n vrcholů. Postačující podmínkou pro T-faktorizaci kompletního grafu K_{2n}, je-li n liché, je smíšené ohodnocení kostry T, které je založeno na existenci rho-ohodnocení a bipartitního rho-ohodnocení, o nichž jsme vyprávěl minule. A právě o smíšeném ohodnoceníbude hovor.

Pozvánka v PDF.

 

5. listopadu     Michael Kubesa: G-dekompozice kompletních grafů

Mějme podgrafy G_1,G_2,...,G_s, kompletního grafu, které jsou všechny izomorfní s grafem G. Patří-li každá hrana kompletního grafu do přesně jednoho podgrafu G_i, pak jde o G-dekompozici kompletního grafu. Postačující podmínkou pro G-dekompozici kompletního grafu K_{2n+1} jsou alpha-ohodnocení, beta-ohodnocení a rho-ohodnocení grafu G s n hranami. A právě o těchto ohodnoceních a bipartitním rho-ohodnocení bude hovor.

Pozvánka v PDF.

 

30. října     Petr Kovář: Hledání handicapových labelingů grafů se sudou pravidelností

Prezentovali jsme známé výsledky týkající se nutných podmínek existence handicapových ohodnocení pravidelných grafů. Zmínili jsme otevřené problémy v této oblasti.

Pozvánka v PDF.

 

22. října     Tereza Kovářová: Konstrukce 3- a 5-pravidelných handicapových grafů

Prezentovali jsme známé výsledky týkající se konstrukcí 3- a 5-pravidelných handicapových grafů. Zformulovali jsme další směr výzkumu.

Pozvánka v PDF.

 

8. října     Petr Kovář: Nutné podmínky existence handicapových grafů

Prezentovali jsme známé výsledky týkající se nutných podmínek existence handicapových ohodnocení pravidelných grafů. Zmínili jsme otevřené problémy v této oblasti.

Pozvánka v PDF.

 

1. října     Petr Kovář: Neúplné turnaje a magická ohodnocení pravidelných grafů

V přednášce shrneme přehled témat, kterým se můžeme věnovat v rámci semináře DiMaS.

Pozvánka v PDF.

 

Abstrakty 2011

21. dubna     Michael Kubesa: Grafová ohodnocení a jejich použití při rozkladech kompletních a bipartitních kompletních grafů

Mějme vzajemně izomorfní pografy G_1,G_2,... ,G_m grafu H (platí tedy G_1 ≅ G_2 ≅ ... ≅ G_m ≅ G). Jestliže každá hrana grafu H je obsažena v přesně jednom podgrafu G_i, i ∈ {1, 2,... , m}, pak hovoříme o G-rozkladu (dekompozici) grafu H. Pokud graf G s n hranami umožňuje tzv. graciózní nebo ρ-ohodnocení, pak existuje G-rozklad kompletního grafu K_{2n+1} a jestliže má G tzv. bipartitní ρ-ohodnocení, pak existuje G-rozklad kompletního bipartitního grafu K_{n,n}.

Pozvánka v PDF.

 

Abstrakty 2009

16. prosince     Roman Kužel: Nelineární iterační metody pro výpočet kritického čísla a hustoty neutronového toku aktivní zóny jaderných reaktorů typu VVER

Přednáška bude věnována problematice řešení difuzního modelu transportu neutronů pro reaktory s kazetami se šestiúhelníkovým průřezem. Zaměříme se především na rychlé nelineární iterační algoritmy založené na hrubosíťovém výpočtu a metodě příčných integrací.

Pozvánka v PDF.

 

15. prosince     Roman Čada: Diskrétní matematika v optimalizaci palivových vsázek jaderného reaktoru

Přednáška bude zaměřena po nezbytném fyzikálním úvodu na matematické metody řešení úlohy optimalizace palivových vsázek v jaderných reaktorech. Ačkoli se ve své podstatě jedná o úlohu nelineární kombinatorické optimalizace, používané metody zahrnují kombinaci přístupů založených na spojité a diskrétní nelineární optimalizaci, stochastických metodách a konceptech užívaných v diskrétní matematice.

Pozvánka v PDF.

 

9. prosince     Martin Knor: Polomerovo Moorovské grafy a digrafy

Graf (digraf) je polomerovo Moorovský ak má pri danom polomere s a maximálnom stupni t maximálny možný počet vrcholov a jeho priemer je nanajvýš s+1. Je známe, že pre každé s a t existuje polomerovo Moorovský digraf daného stupňa a polomeru. Pre grafy je analogický problém otvorený. Polomerovo Moorovské grafy sú známé pre každý stupeň t pri polomeroch 1 a 2 a pre niekolko malých stupňov pri polomere 3.

Pozvánka v PDF.

 

1. prosince     Petr Kovář: Simpsonovi a matematika

V oblíbeném televizním seriálu najdeme celou řadu momentů, ve kterých se objeví základní i moderní matematické pojmy. V přednášce na několik takových míst upozorníme. Současně naznačíme některé hlubší souvislosti.
Přednáška může být zajímavá nejen pro studenty, ale i pro vyučující (motivace ve výuce).
Kalkulačky s sebou!!!

Pozvánka v PDF.

 

25. května     S. Arumugam: Min-Max and Max-Min Graph Saturation Parameters

A talk on hereditary property concerning subsets of the vertex set of a graph G. In this talk a brief survey of results on certain parameters for various graph theoretic properties is given.

Pozvánka v PDF.

 

Více...

Od roku 2009 jsou abstrakty připravovány pouze v PDF formátu.

Staší abstrakty najdete pouze v anglické verzi.

---

kontakty

Poslední úpravy: 04.07.2023