Journées de Lancement - Résumés des exposés jeunes chercheurs
Tereza Klimosova (Jeudi, 11h)
Titre : Infinite dimensional finitely forcible graphon
Résumé : Graphons are analytic objects associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible. We show that there exists a finitely forcible graphon such that the topological space of its typical vertices has infinite Lebesgue covering dimension, disproving the conjecture by Lovasz and Szegedy. The talk is based on joint work with Roman Glebov and Dan Kral.
Clément Charpentier (Jeudi, 11h30)
Titre : Nordhaus-Gaddum inequality for the game chromatic number
Résumé : A result from Nordhaus and Gaddum states that, for any graph G of order n, X(G) + X(-G) ≤ n + 1 where -G is the complementary of G. We give a similar bound for the game chromatic number of G, which is the smallest integer k such that one can color G with k colors taking turn with an uncooperative partner (this is called the coloring game). Joint work with Ana Luísa C. Furtado and Sylvain Gravier
Leandro Ishi Lima (Vendredi, 11h)
Titre : The Spliced Alignment Problem and its Variants
Résumé : In this presentation, we firstly introduce a known problem called the Spliced Alignment Problem (SAP), proposed by Gelfand et al. in [1]. In a nutshell, the SAP receives as input two strings g and t, and a set B of substrings of g, and the objective is to find a chain of strings from B such that the similarity between the concatenated chain and t is as high as possible. This problem can be applied in bioinformatics, where g is a genomic sequence encoding an unknown gene, B contains the putative exons from g and t is an annotated cDNA and the objective is to find the multiexon structure from B with the best fit to the related cDNA. After a brief formal definition, motivation, and solution of this problem, we introduce and study some theoretical properties of several variations: the Multiple Spliced Alignment Problem, the Two-dimensional Chain Problem, the Chain Alignment Problem, and the Multiple Chain Alignment Problem.
[1] Gelfand, M. S., Mironov, A. A., and Pevzner, P. A. Gene recognition via spliced sequence alignment. In Proceedings of the National Academy of Sciences 93 (1996), 9061–9066.
Antoine Dailly (Vendredi, 11h30)
Titre : Octal Games on Graphs: 0.03 and 0.33
Résumé : Octal games are a set of combinatorial games (two-player games with no chance, perfect information, no loops, no draw, and where the winner is determined by the last move) played on heaps of counters and whose rules are fully described by an octal code. We generalize their definition in order to play octal games on graphs.
0.03 is a game where a player can delete two adjacent vertices and all their adjacent edges from a graph, without disconnecting it. We show a winning strategy for trees, 2xn grids and 3xn grids. 0.33 is a game where a player can delete one or two adjacent vertices and all their adjacent edges from a graph, without disconnecting it. We find a resolution of this game for a subclass of trees.
Ghizlane Echbarthi (Vendredi, 15h)
Titre : Online methods for massive graph partitioning
Résumé : Graph partitioning is an important challenging problem when performing computation tasks over large distributed graphs, for a good partitioning leads to faster computations. In this work, we first introduce a new streaming partitioning heuristic and show that it outperforms the state-of-the-art heuristics for streaming partitioning, giving exactly balanced partitions with lower cut. Secondly, we introduce the Online Metis Partitioning method (OMP) which is an online version of METIS, a fast and well known multilevel heuristic for graph partitioning. Our experiments show that the OMP method yields partitions of similar quality when compared to the offline setting of METIS and outperforms the other online methods.
William Lochet (Vendredi, 15h30)
Titre : AVD colouring and entropy compression
Résumé : A proper edge colouring of a graph G is adjacent vertices distinguishing or an avd-colouring if the set of colours incident to x is different from the set of colours incident to y whenever (x,y) is an edge of G. Let d be the maximum degree of G. It was conjectured by Zhang Liu and Wang that, if G is not an isolated edge or a cycle of length 5, then d+2 colours is enough to obtain an avd-colouring. With multiple use of the local lemma, Hatami proved the upper bound d+300. Using the entropy compression method, we show that d+20 is enough.
Joint work with Gwenaël Joret.