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

Past terms

Fall 2019

Spring 2019

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₂(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₂(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₂(n,K4-) for infinitely many values of n. In fact, we show that determining the exact value of ex₂(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.