# Joint DIMEA and FORMELA seminar

This research seminar provides a venue for presenting research results concerning algorithms, discrete structures, formal methods, logic and related areas of theoretical computer science. The seminar is jointly organized by the research laboratories DIMEA and FORMELA. The seminar builds on the FMDSA seminar organized by the FORMELA laboratory in the past.

#### Time and place

The seminar takes place on Monday at 2PM term time in Room C417 in the building of the Faculty of Informatics on a (roughly) biweekly schedule.

## Spring 2020 – schedule overview

February 10 | Alexander Rabinovich (Tel Aviv University) | On degree of ambiguity of finite state automata |

February 24 | Théo Pierron (Masaryk University) | Some Brooks-like results for graph powers |

March 2 | Matjaž Krnc (University of Primorska) | On avoidable paths in graphs |

March 9 | Jan Volec (Czech Technical University) | The co-degree threshold of K4- |

## Past terms

#### Alexander Rabinovich (Tel Aviv University): On degree of ambiguity of finite state automata

##### Monday 10 February, 14:00, room C417

An automaton is unambiguous if for every input it has at most one
accepting computation. An automaton is k-ambiguous if for every
input it has at most k accepting computations. An automaton is
boundedly ambiguous if it is k-ambiguous for some k. An automaton
is finitely (respectively, countably) ambiguous if for every
input it has at most finitely (respectively, countably) many
accepting computations.

For automata over finite words (and over finite trees), on every
input there are at most finitely many accepting computations.
Hence, every automaton on finite words and on finite trees is
finitely ambiguous. However, over infinite-words and over
infinite trees there are nondeterministic automata with
uncountably many accepting computations.

In this talk I survey recent results about degree of ambiguity of
automata and regular languages.

#### Théo Pierron (Masaryk University): Some Brooks-like results for graph powers

##### Monday 24 February, 14:00, room C417

Given an integer k, coloring the k-th power of a graph means assigning colors to its vertices in such a way that vertices at distance at most k receive different colors. When k is 1, we get the standard notion of coloring, and Brooks' theorem states that every connected graph of maximum degree D>2 besides the clique on D+1 vertices can be colored using D colors (i.e. one color less than the naive upper bound). For k>1, a similar result holds: excepted for Moore graphs, the naive upper bound can be lowered by 2. In this talk, we will show how to extend these results in order to spare more colors when k increases.

#### Matjaž Krnc (University of Primorska): On avoidable paths in graphs

##### Monday 2 March, 14:00, room C417

A vertex v in a graph G is avoidable if every induced path on three
vertices with middle vertex v is contained in an induced cycle. G. Dirac
(1961) showed that every chordal graph has such a vertex, and Ohtsuki et al.
(1976) showed an existence of an avoidable vertex for every graph.
Beisegel et al. (2019) generalized this notion to avoidable paths, and
Bonamy et al. (2019+) showed that for every positive integer k, every
graph containing an induced P_{k} also contains an avoidable
P_{k}. This generalizes the mentioned results regarding avoidable
vertices, as well as the one by Chvátal et al. (2002) on the existence of
simplicial paths. In this talk, we show that for every positive integer k
and every graph G, every induced P_{k} from G can be shifted to an
avoidable P_{k}. Joint work with V. Gurvich, M. Milanič, and M. Vyalyi.

#### Jan Volec (Czech Technical University): The co-degree threshold of K4-

##### Monday 9 March, 14:00, room C417

The co-degree threshold ex_{2}(n,F) of a 3-uniform hypergraph F is the minimum d
such that every 3-uniform hypergraph on n vertices in which every pair of
vertices is contained in at least d+1 edges contains a copy of F as a subgraph.
In this talk, we focus on the co-degree threshold of K4-, the unique 3-uniform
hypergraph with 4 vertices and 3 edges.
Using flag algebras, we show that ex_{2}(n,K4-) = n/4+O(1) which confirms a
conjecture of Nagle from 1999. Moreover, we show that for every near-extremal
3-uniform hypergraph H, there exists a quasi-random tournament T on the same
vertex-set such that H is close in the edit distance to the hypergraph of
cyclically oriented triangles of T. That yields a very close relation of the
K4- co-degree threshold and the existence of skew Hadamard matrices, which
allows us to determine the exact value of ex_{2}(n,K4-) for infinitely many
values of n. In fact, we show that determining the exact value of ex_{2}(n, K4-)
for n=4k+3 is equivalent to Seberry's conjecture stating that a skew Hadamard
matrix exists for every n=4k.
This is a joint work with Victor Falgas-Ravry, Oleg Pighurko and Emil Vaughan.