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-|
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
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.
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.
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 Pk also contains an avoidable Pk. 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 Pk from G can be shifted to an avoidable Pk. Joint work with V. Gurvich, M. Milanič, and M. Vyalyi.
Monday 9 March, 14:00, room C417
The co-degree threshold ex2(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 ex2(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 ex2(n,K4-) for infinitely many values of n. In fact, we show that determining the exact value of ex2(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.