~~NOCACHE~~ /* DO NOT EDIT THIS FILE */ [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday December 14, 2021, 3PM, Salle 1007\\ **Laurent Beaudou** (HSE) //Of points and lines// \\ Given n points in the Euclidean plane, they are either all collinear or define at least n distinct lines. This result is a corollary of the Sylvester-Gallai theorem. Its combinatorial generalization was proven by de Bruijn and Erdös in the forties. In 2008, Chen and Chvátal described a generalization of the notion of a line to any metric space and conjectured that the same result remains true in that framework. Since then, a growing community of researchers has been investigating this question. It remains open for metric spaces and even for those specific metric spaces generated by graphs. In this talk, we shall see a broad overview of the state of research on the matter: results and (many!) remaining open questions. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday November 30, 2021, 2PM, Salle 1007\\ **Marco Caoduro** (G-Scop) //Hitting and packing squares// \\ Let $\mathcal{S}$ be a family of (not necessarily axis parallel) squares in the plane. The \emph{transversal number} of $\mathcal{S}$, denoted by $\tau(\mathcal{S})$, is the minimum number of points needed to hit all the squares in $\mathcal{S}$, and the \emph{independence number} of $\mathcal{S}$, denoted by $\nu(\mathcal{S})$, is the maximum number of pairwise disjoint squares in $\mathcal{S}$. Clearly, $\tau(\mathcal{S})$ is at least $\nu(\mathcal{S})$. We prove that $\tau(\mathcal{S}) \leq 10 \nu(\mathcal{S})$ and present a family where $\tau(\mathcal{S}) = 3\nu(\mathcal{S})$. During the talk, we will sketch the proof of the main result and remark how to extend our approach to families of rectangles with \emph{bounded aspect ratios}. This is joint work with András Sebő. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday November 9, 2021, 2PM, Salle 1007\\ **Subir Kumar Ghosh** (RKMVERI) //Chromatic art gallery problems for point and vertex guards// \\ The art gallery problem is to determine the number of guards (or surveillance cameras) sufficient to cover or see every point in the interior of an art gallery. An art gallery can be viewed as a polygon P (with or without holes) with a total of n vertices, and guards as points in P. Any point z in P is said to be visible from a guard g if the line segment joining z and g does not intersect the exterior of P. This problem was first posed by Victor Klee in a conference in 1973, and in the course of time, it has become an important problem in computational geometry with extensive applications to surveillance of buildings like airport terminals, railway stations etc. A polygon is said to be guarded by a set of chosen guards if every interior point of P is visible from some guard within the guard set. Chromatic art gallery problems arise from applications in areas like landmark-based robot navigation and wireless networks. One such problem is the weak-conflict free guarding of polygons, where the objective is to colour a chosen guard set S for P using the minimum number of colours such that each point within P sees at least one guard from S with a unique colour. Note that the objective here is to minimize the number of colors rather than the number of guards in S. We present an algorithm for weak conflict-free guarding of P (without holes) where the point guard set is coloured using only O(log n) colours. If the guards are allowed to place only on vertices of P, the corresponding algorithm for weak conflict-free vertex guarding problem uses O(log^2 n) colours. This algorithm uses funnel structures of weak visibility polygons for placing coloured guards. Finally, we discuss a few open problems on weak conflict-free guarding of P for both point and vertex guards. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday October 26, 2021, 2PM, Salle 1007\\ **Sagnik Sen** (IIT Dharwad, India) //On homomorphisms of simple signed graphs of some families// \\ A signed graph $(G, \sigma)$ is a graph $G$ along with a function $\sigma: E(G)\to\{+,-\}$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The chromatic number (this is one of the many notions of chromatic number for signed graphs available in literature) of a signed graph $(G, \sigma)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H, \pi)$ to which $(G, \sigma)$ admits a homomorphism. Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the chromatic number. In this work, we provide new results and bounds on the chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs). Joint work with: Bensmail, Das, Nandi, Pierron, Sopena [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday October 19, 2021, 2PM, Salle 1007 and via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]\\ **Mirna Džamonja** (IRIF) //On limits-from the finite to the countable and very much uncountable graphs// \\ We survey several different methods of constructing infinite graphs out of the families of finite graphs, among the Fraîssé limits, the morasses, the ultraproducts and the graphons/measurings. Concentrating on a couple of them, we talk about various colourings and the generalised Ramsey theory. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday October 5, 2021, 2PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]\\ **Daniel Gonçalves** (CNRS, Université de Montpellier) //Segment representation of planar graphs// \\ A segment intersection representation of a graph is a set of segments such that each vertex corresponds to a segment, and such that two segments intersect if and only if the corresponding vertices are adjacent. There exists several proofs that bipartite planar graphs admit segment intersection representation, whose segments are either horizontal or vertical. Furthermore, the representation is such that parallel segments correspond to an independent set. In his PhD Thesis E.R. Scheinerman conjectured that every planar graph has a segment intersection representation, and he also conjectured that in the case of 3-colorable planar graphs, such a representation exists where only 3 slopes appear, one for each color class. We proved both of these conjectures, and we also proved that such a representation with 4 slopes, one per color class, does not always exist. This last proof relies on the fact that planar signed graphs are not always four colorable, for some signed version of colorings. During the talk we will provide the general idea of these proofs. These works were joint works with J. Chalopin, L. Isenmann, and C. Pennarun [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Thursday June 24, 2021, 10AM, 3052 and [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 | ZOOM]]\\ **David Roberson** (Department of Applied Mathematics and Computer Science, Technical University ofDenmark) //Quantum isomorphism and counting homomorphisms from planar graphs// \\ In the "isomorphism game", two separated but collaborating players attempt to convince a referee that a given pair of graphs are isomorphic. Any perfect classical strategy for this game corresponds to an isomorphism of the graphs. Thus two graphs are said to be "quantum isomorphic" if the players can win the corresponding isomorphism game using a quantum strategy, i.e., one in which the players can make local measurements on a shared quantum state. Surprisingly, two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. This can be viewed as a quantum analog of a classical theorem of Lovasz stating that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. A notable aspect of this characterization of quantum isomorphism is that its proof relies heavily on tools from quantum group theory, and thus it provides a link between this field and those of quantum information and combinatorics. Additionally, this characterization can be used to show that the Four Color Theorem is equivalent to every planar graph having a homomorphism to a particular graph on 24 vertices. It remains to be seen whether this last result is actually interesting. This is joint work with Laura Mančinska. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday May 25, 2021, 2PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]\\ **Adrian Pastine** (Universidad Nacional de San Luis) //Null Decomposition of Graphs// \\ Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices. In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time. This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday May 11, 2021, 2PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 |ZOOM]]\\ **Bérénice Delcroix-Oger** //Parking trees// \\ In 1980, Edelman defined a poset on objects called noncrossing 2-partitions, made of a partition and a noncrossing partition, with a bijection linking parts of the same size in both partitions. Studying this poset, he proved that the number of noncrossing 2-partitions is given by (n+1)^{n-1}. This is also the number of classical combinatorial objects called parking functions. After introducing noncrossing partitions, noncrossing 2-partitions and parking functions, we will draw the link between parking functions and noncrossing 2-partitions, describing Edelman's poset in terms of parking functions. Afterwards, we will (recall and) use the notion of species introduced in the early 1980s by Joyal to describe the action of the symmetric group on a poset on parking trees. This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo. This would be a joint (Combi-Graph) seminar. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday April 27, 2021, 3PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]\\ **Daniel Adolfo Quiroz** //Colouring with conditions on distances// \\ A natural variant of proper vertex colorings, consists in considering colorings which require different colours for vertices at distance (exactly) p, for some fixed p. For that type of colouring, the answer to the question "how many colours suffice?", can depend greatly on the parity of p. In the talk I will give an overview of the results on this type of colouring, focusing particularly in the case of planar graphs. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday April 13, 2021, 3PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]\\ **Adrian Pastine** (Universidad Nacional de San Luis) //Null Decomposition of Graphs// \\ Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices. In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time. This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday March 16, 2021, 2PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09| ZOOM]]\\ **Filippo Brunelli** (IRIF) //On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks// \\ A weighted point-availability time-dependent network is a list of temporal edges, where each temporal edge has an appearing time value, a travel time value, and a cost value. We consider the single source Pareto problem in weighted point-availability time-dependent networks, which consists of computing, for any destination $d$, all Pareto optimal pairs $(t,c)$, where $t$ and $c$ are the arrival time and the cost of a path from $s$ to $d$, respectively (a pair $(t,c)$ is Pareto optimal if there is no path with arrival time smaller than $t$ and cost no worse than $c$ or arrival time no greater than $t$ and better cost). We design and analyse a general algorithm for solving this problem, whose time complexity is $O(M\log P)$, where $M$ is the number of temporal edges and $P$ is the maximum number of Pareto optimal pairs for each node of the network. This complexity significantly improves the time complexity of the previously known solution. Our algorithm can be used to solve several different minimum cost path problems in weighted point-availability time-dependent networks with a vast variety of cost definitions, and it can be easily modified in order to deal with the single destination Pareto problem. Meeting ID: 894 0889 8417 Passcode: 005585 [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday March 2, 2021, 2PM, Online Via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 | ZOOM]]\\ **Stephane Devismes** (VERIMAG U. Grenoble Alpes) //Self-stabilizing Systems in Spite of High Dynamics// \\ A self-stabilizing distributed system, regardless its initial configuration, converges within finite time to a configuration from which its behavior is correct. By essence, self-stabilization is a non-masking fault tolerant approach since the arbitrary initial configuration can be seen as the result of arbitrary transient faults. In this talk, we will consider self-stabilization in highly dynamic networks, i.e., networks suffering from unexpected and frequent topological changes. Precisely, assuming that nodes are uniquely identified, we study the self-stabilizing leader election problem in three important classes of dynamic networks to obtain solutions tolerating both transient faults (such as memory corruption) and frequent topological changes. We first study conditions under which our problem can be solved and then propose several algorithms. Our results reveal that the assumption on the knowledge of the number N of processes is central. Indeed, we show that, as soon as there is no strong guarantees on the temporal connectivity in the network, the knowledge of the exact value of N is required. Finally, the convergence time of self-stabilizing leader election cannot be bounded in some important cases. In those cases, we show that our solutions are speculative since their convergence time can be still bounded in a subset of more probable executions. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Thursday February 25, 2021, 2PM, Online, via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 |Zoom]]\\ **Matej Stehlik** (G-SCOP) //Critical subgraphs of Kneser graphs// \\ The Kneser graph KG(n,k) is the graph whose vertex set consists of all k-subsets of an n-set, with edges joining pairs of disjoint subsets. Kneser graphs arise naturally in various contexts, and play a central role in fractional colouring. In 1978, Lovasz used tools from algebraic topology to prove that KG(n,k) is (n-2k+2)-chromatic, proving a long-standing conjecture of Kneser and laying the foundations of topological combinatorics. Shortly thereafter, Schrijver defined an induced subgraph SG(n,k) of KG(n,k), known as the Schrijver graph, and showed that SG(n,k) is also (n-2k+2)-chromatic. Moreover, he showed that SG(n,k) is vertex-critical, in the sense that the chromatic number decreases if any vertex is deleted. However, Schrijver graphs are in general not edge-critical: certain edges can be deleted without any effect on the chromatic number. In this talk, I will define an (n-2k+2)-chromatic edge-critical subgraph of SG(n,k), thereby sharpening the classical results of Lovasz and Schrijver. Joint work with Tomas Kaiser. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday February 23, 2021, 2PM, Online, via [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 |Zoom]]\\ **Arnau Padrol** (Institut de Mathématiques de Jussieu) //Sweeps, polytopes, oriented matroids, and allowable graphs of permutations// \\ A sweep of a point configuration is an ordered partition induced by a linear functional. These orders are at the core of several applications in discrete and computational geometry, and also appear naturally in linear programming. The set of orderings obtained this way is highly structured: isomorphic to the face lattice of a convex polytope. In the plane, they were formalized and abstracted by Goodman and Pollack under the theory of allowable sequences of permutations, but a high dimensional generalization was missing. I will present an overview of the theory, discuss polytopal constructions, and introduce combinatorial generalizations in terms of oriented matroids and allowable graphs of permutations. This is based on joint work with Eva Philippe. https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday February 2, 2021, 2PM, Salle 3052 and [[ https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09|ZOOM]]\\ **Zhouningxin Wang** (IRIF) //Density of C_{-4}-critical signed graphs// \\ By extending the notion of indicator to signed graphs, we show the problem of 4-coloring is captured by the problem of C_{-4}-coloring (mapping signed graphs to a negative 4-cycle). Moreover, we extend the notion of H-critical to (H, \pi)-critical. In this talk, we prove that any C_{-4}-critical signed graph on n vertices, except for one particular signed bipartite graph on 7 vertices and 9 edges, must have at least 4n/3 edges. As an application to planarity, we conclude that every signed bipartite planar graph of negative girth at least 8 admits a homomorphism to C_{-4} and show that this bound is the best possible, which is relevant to a bipartite analog of Jaeger-Zhang conjecture. Zoom link: https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09 Meeting ID: 894 0889 8417 Passcode: 005585 [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday January 12, 2021, 3PM, Online\\ **Benjamin R. Moore** (University of Waterloo) //The Pseudoforest Nine Dragon Tree conjecture is true// \\ I will give an overview of the following result. Let k and d be integers. Let G be a graph with maximum average degree at most 2k + 2d/(k+d+1). Then G decomposes into k+1 pseudoforests such that one of the pseudoforests has each connected component containing at most d edges. Here a pseudoforest is a graph where each component contains at most one cycle, and a decomposition is a partition of the edge set into edge disjoint subgraphs. By a result of Fan et al., the bound is best possible for all k and d, even when you ask for one pseudoforest with maximum degree at most d. This is joint work with Logan Grout.