Speakers: Gábor Simonyi, Gábor Tardos
Codes with graphs as codewords (14:00-15:00)
Abstract: The most basic problem in coding theory is to determine the maximum size of a set of binary sequences of a given length so that their pairwise Hamming distance is at least some prescribed value. But what happens if our binary sequences (having length {n choose 2}) are characteristic vectors of the edge sets of graphs on a fixed n-element vertex set? Then we may ask questions that take into account the structure of the graphs we obtain when we take the modulo 2 sum of a pair of our sequences and consider the result again as the characteristic vector of (the edge set of) a graph on the given vertex set. We obtain questions like: How many graphs can we give on a fixed n-element vertex set if the symmetric difference (defined by the symmetric difference of their edge sets) of any two of them contains a triangle? Or a Hamiltonian cycle? Or a spanning star?
In the talk we will answer (at least partially) some questions of the above type. I also plan to mention some problems where the codewords are not graphs but related combinatorial structures.
Most of the talk will be based on a paper joint with Noga Alon, Anna Gujgiczer, János Körner and Aleksa Milojević.
Extremal theory of vertex- and edge-ordered graphs (16:00-17:00)
Abstract: Turán type extremal graph theory has a long history and lot of applications. It was also generalized in several directions including hypergraphs oriented graphs, geometric graphs, etc. This talk is a survey of recent results in two of these generalizations: the extremal theories of vertex- and edge-ordered graphs. A vertex-ordered graph is simple graph together with a specified linear order on vertices. In the extremal theory we are looking for the maximal number of edges in an n-vertex vertex-ordered graph that does not contain a specified "forbidden" vertex-ordered graph. In other words we want to avoid a specified subgraph with a specified vertex-order, but containing an isomorphic subgraph with a different vertex order is okay. Edge-ordered graphs and their extremal theory is defined similarly but with a linear order on the edges. The talk will contain many recent results and open problems in both theories and highlight some similarities and differences between the two theories.