Thomas Bellitto




bellitto(at)imada.sdu.dk

Tel. +45 6550 2346

Dept. of Mathematics & Computer Science
University of Southern Denmark
Campusvej 55
DK-5230 Odense M
Denmark

Current work and publications

Talks

Teaching

Other

I am a postdoc at IMADA, University of Southern Denmark in Odense. I am part of the project Packing, covering and partitions of digraphs directed by Jørgen Bang-Jensen. My works involve graph theory, combinatorial optimisation, operations research, algorithmics, complexity theory and geometry.

Current work and publications:

Full paper here.

DP-coloring is a relatively new coloring concept by Dvořák and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of finding a list-coloring of a given graph G with a list-assignment L to finding an independent transversal in an auxiliary graph whose vertices are the pairs (v,c) with v in V(G) and c in L(v). In this paper, we extend the definition of DP-colorings to digraphs using the approach from Neumann-Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we prove a Brooks’ type theorem regarding the DP-chromatic number, which extends various results on the (list-)chromatic number of digraphs.

Full document here.

This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs.

We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees.

A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger-Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number.

Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.

Full paper here.

A subset A of R² is said to avoid distance 1 if for all x and y in A, ||x-y||≠1. In this paper we study the number m_1(R²) which is the supremum of the upper densities of measurable sets avoiding distance 1 in the Euclidean plane. Intuitively, m_1(R²) represents the highest proportion of the plane that can be filled by a set avoiding distance 1. This parameter is related to the fractional chromatic number χ_f(R²) of the plane.

We establish that m_1(R²) ≤ 0.25646 and χ_f(R²) ≥ 3.8992.

Full paper here. (shorter version available in the conference proceedings of WG 2018)

A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.

Full paper here.

For oriented graphs G and H, a homomorphism f: G → H is locally-injective if, for every v in V(G), it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of v. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when H is a reflexive tournament on three or more vertices with a loop at every vertex, and Polynomial when H is a reflexive tournament on two or fewer vertices.

Full paper here.

The maximal density of a measurable subset of R^n avoiding Euclidean distance 1 is unknown except in the trivial case of dimension 1. In this paper, we consider the case of a distance associated to a polytope that tiles space, where it is likely that the sets avoiding distance 1 are of maximal density (1/2)^n, as conjectured by Bachoc and Robins. We prove that this is true for n=2, and for the Voronoï regions of the lattices A_n, n≥2.

Full paper here. (shorter version available in the conference proceedings of AAIM 2016)

This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known, but traffic monitoring presents new challenges that the previous models of separation fall short from modelling such as taking into account the multiplicity and order of the arcs in a walk. We introduce a new and stronger model of separation based on languages that generalises the traffic monitoring problem. We study three subproblems with practical applications and develop methods to solve them by combining integer linear programming, separating codes and language theory.

Full paper here. (shorter version available in the conference proceedings of the German Conference on Bioinformatics 2015)

Despite most recent advances in structural variation discovery, many variants are yet to be discovered. Midsize insertions and deletions pose particularly involved algorithmic challenges. A prior method of ours (CLEVER) pointed out new ways. However, the resulting read alignment clusters tend to be too small and are heavily overlapping, which leads to losses in recall performance rates. Here we present a model based on \emph{weighted cluster editing}, which alleviates these issues: clusters are provably non-overlapping and tend to be larger. In order to render the inherent optimization problem tractable on all, and not just discordant, read alignment data of a genome, we present a novel, principled heuristic, which solves the problem in time linear in the length of the genome. The heuristic is based on an exact polynomial-time algorithm for weighted cluster editing in one-dimensional point graphs. We demonstrate that the new model improves recall rates achieved by CLEVER.

Talks:

International conferences:

National conferences:

Seminars:

Teaching:

University of Bordeaux:

Advising:

Other: