On counting orientations for graph homomorphisms and for dually embedded graphs using the Tutte polynomial of matroid perspectives. Submitted (8 pages note). Note. (slightly) completed journal version for [P04]
Download: not available at the moment, see [P04].
The goal of this note is to highlight applications to graph orientations of some recent results in oriented matroid perspectives, by providing adapted settings and a detailed example. An (oriented) matroid perspective (or morphism, or strong map, or quotient) is an ordered pair of (oriented) matroids satisfying some structural relationship. In the case of graphs, two notable types of perspectives can be considered: graph homomorphisms, and dually embedded graphs on a surface. The Tutte polynomial of such a perspective is a classical polynomial (also called Las Vergnas polynomial in the case of dually embedded graphs), whose coefficients and (some) evaluations are known to count pairs of orientations of certain types. We show how coefficients and (other) evaluations of the polynomial also count pairs of orientations of certain types where some edge orientations are fixed, as well as some equivalence classes of pairs of orientations of certain types. These properties appear when the edge set is linearly ordered. Keywords: Graph orientations, Graph embedding, Graph homomorphism, Matroid perspective, Strong map, Matroid morphism, Oriented matroid, Tutte polynomial
Short rewriting, and geometric explanations related to the active bijection, for [Extension-lifting bijections for oriented matroids, by S. Backman, F. Santos, C.H. Yuen, arXiv:1904.03562v2]. Preprint, submitted (8 pages note). Download: author version. Deposit/Metadata: arXiv:2312.07522.
For an oriented matroid M, and given a generic single element extension and a generic single element lifting of M, the main result of [1] provides a bijection between bases of M and certain reorientations of M induced by the extension-lifting. This note is intended to somehow clarify and precise the geometric setting for this paper in terms of oriented matroid arrangements and oriented matroid programming, to describe and prove the main bijective result in a short simple way, and to show how it consists of combining two direct bijections and a central bijection, which is the same as a special case - practically uniform - of the bounded case of the active bijection [5, 6]. (The relation with the active bijection is addressed in [1] in an indirect and more complicated way.)
Active decomposition of matroid bases, and Tutte polynomial in terms of beta invariants of minors. With Michel Las Vergnas (Rip). Submitted (27 full pages). Note. Updated version of the preprint arXiv 1807.06516. (Initially called "The active bijection 2.a ...", but the papers in the series have been reorganized since then.)
[ABSTRACT BEFORE UPDATE] We introduce and study filtrations of a matroid on a linearly ordered ground set, which are particular sequences of nested sets. A given basis can be decomposed into a uniquely defined sequence of bases of minors, such that these bases have an internal/external activity equal to 1/0 or 0/1 (in the sense of Tutte polynomial activities). This decomposition, which we call the active filtration/partition of the basis, refines the known partition of the ground set into internal and external elements with respect to a given basis. It can be built by a certain closure operator, which we call the active closure. It relies only on the fundamental bipartite graph of the basis and can be expressed also as a decomposition of general bipartite graphs on a linearly ordered set of vertices. From this, first, structurally, we obtain that the set of all bases can be canonically partitioned and decomposed in terms of such bases of minors induced by filtrations. Second, enumeratively, we derive an expression of the Tutte polynomial of a matroid in terms of beta invariants of minors. This expression refines at the same time the classical expressions in terms of basis activities and orientation activities (if the matroid is oriented), and the well-known convolution formula for the Tutte polynomial. Third, in a companion paper of the same series (No. 2.b), we use this decomposition of matroid bases, along with a similar decomposition of oriented matroids, and along with a bijection in the 1/0 activity case from a previous paper (No. 1), to define the canonical active bijection between orientations/signatures/reorientations and spanning trees/simplices/bases of a graph/real hyperplane arrangement/oriented matroid, as well as various related bijections.
The Active Bijection 2 - Active decomposition of oriented matroids, general definitions and main properties of the active bijection. With Michel Las Vergnas (Rip). Publication process started over because of some updates/reorganization and of the paper length (intially 58 full pages). Note. Updated version of the preprint arXiv 1807.06578. (Initially called "The active bijection 2.b ...", but the papers in the series have been reorganized since then.)
[ABSTRACT BEFORE UPDATE] The active bijection for oriented matroids (and real hyperplane arrangements, and graphs, as particular cases) is introduced and investigated by the authors in a series of papers. Given any oriented matroid defined on a linearly ordered ground set, we exhibit one particular of its bases, which we call its active basis, with remarkable properties. It preserves activities (for oriented matroids in the sense of Las Vergnas, for matroid bases in the sense of Tutte), as well as some active partitions of the ground set associated with oriented matroids and matroid bases. It yields a canonical bijection between classes of reorientations and bases (this bijection depends only on the reorientation class of the oriented matroid, that is on the non-signed pseudosphere arrangement in terms of a topological representation). It also yields a refined bijection between all reorientations and subsets of the ground set. Those bijections are related to various Tutte polynomial expressions (in terms of usual and refined activities for bases/subsets or reorientations, in terms of beta invariants of minors). They contain various noticeable bijections involving orientations/signatures/reorientations and spanning trees/simplices/bases of a graph/real hyperplane arrangement/oriented matroid. For instance, we obtain an activity preserving bijection between acyclic reorientations and no-broken-circuit subsets. In previous papers of this series, we defined the active bijection between bounded regions and uniactive internal bases by means of fully optimal bases (No. 1), and we defined a decomposition of activities for matroid bases by means of active filtrations (or active partitions) yielding particular sequences of minors (companion paper, No. 2.a). The present paper is central in the series. First, we define a decomposition of activities for oriented matroids, using the same sequences of minors, yielding a decomposition of an oriented matroid into bounded regions of minors. Second, we use the previous results together to provide the canonical and refined active bijections alluded to above. We also give an overview and examples of the various results of independent interest involved in the construction. They arise as soon as the ground set of an oriented matroid is linearly ordered.
The Tutte polynomial of oriented matroids. Handbook of the Tutte Polynomial and Related Topics, Chapter 31, J. Ellis-Monaghan and I. Moffatt ed., Chapman and Hall/CRC, 25 p., 2022. Download: not available at the moment. Publisher site: here. Deposit/Metadata: HAL-lirmm-03868723. Citation: BibTeX.
This chapter covers properties of the Tutte polynomial for oriented matroids. It covers the basics of oriented matroids, as well as their interactions with the Tutte polynomial. Oriented matroids, interpretations and translations in hyperplane arrangements and in directed graphs. The Tutte polynomial in terms of orientation-activities, generalization to oriented-matroid perspectives, and a 4-variable expansion. Geometric interpretations of the β-invariant, of the other coefficients, and of particular evaluations. Expression of the Tutte polynomial of a matroid in terms of active filtrations/partitions and β-invariants of minors. Activity-preserving bijections between bases/subsets/no-broken-circuit-subsets and activity-classes/reorientations/regions. Circuit/cocircuit reversal classes in directed graphs and regular matroids. Keywords: Oriented matroid, Hyperplane arrangement, Regular matroid, Directed graph, Orientation activities, Tutte polynomial
The Tutte polynomial of matroid perspectives. Handbook of the Tutte Polynomial and Related Topics, Chapter 28, J. Ellis-Monaghan and I. Moffatt ed., Chapman and Hall/CRC, 18 p., 2022. Download: not available at the moment. Publisher site: here. Deposit/Metadata: HAL-lirmm-03868715. Citation: BibTeX.
This chapter covers the Tutte polynomial of matroid perspectives. Matroid perspectives adapt the idea of morphisms to matroid theory. The Tutte polynomial of a matroid perspective is a three-variable generalization of the Tutte polynomial that shares many of its properties. Definition of matroid perspectives, or matroid strong maps. Tutte polynomial generalized to matroid perspectives and various expansions. Structural and enumerative properties in terms of subset activities when the ground set is linearly ordered. Extensions to matroid perspectives of classical counting results. Applications, evaluations, computational complexity, and related polynomials. Keywords: Matroid, Perspective, Morphism, Strong map, Quotient map, Graph homomorphsim, Tutte polynomial
A Qualitative Reasoning Model for Software Testing, based on Combinatorial Geometry. With Spyros Xanthakis. Artificial Intelligence Methods for Software Engineering, Chapter 12, M. Kalech, R. Abreu and M. Last. eds, World Scientific, pp.331-367, 2021. Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-03371990. Citation: BibTeX.
[Introduction] Let us first give a short summary of the paper. We introduce an operational qualitative model for numerical algorithms. This model enables qualitative algorithmic reasoning during the unit testing process, supported by an automatic generation of boundary test data. It contains the spatial encoding of all the functionally equivalent regions (called homodromies). The model, viewed as a qualitative abstraction of the algorithm, is automatically generated thanks to multiple targeted executions of its instrumented basic conditions, that permit the interpolation of a set of linear equations and their corresponding hyperplanes. All feasible paths (when all basic conditions are linear) are identified in the form a Ternary Decision Tree. Each feasible execution path corresponds to a geometric region supported and/or delimited by a finite set of hyperplanes of the vector space. Oriented Matroids allow the encoding of the relative positions of all such regions of various dimensions, in a purely combinatorial way, using a finite signed set system, supported by a rich mathematical theory. This model uses a qualitative space algebra and enables qualitative reasoning: regions are identified according to qualitatively valued inputs, which are, in their turn, propagated through them. The proposed model permits a global/local envisionment of the algorithmic behaviour in an abstract level. The cocircuits of the underlying oriented matroid play the role of testing building blocks: the combination of their numerical coordinates enables the automatic generation of limit boundary data that lies at the boundary of any critical surface of any dimension.
Eléments de théorie des matroïdes et matroïdes orientés. With Jorge Ramirez-Alfonsin. Informatique Mathématique - Une photographie en 2013, Chapitre 2, Philippe Langlois ed., Presses Universitaires de Perpignan, pages 47-95, 2013. Note. Document in French. (Course given at a school for french Ph.D. students.)
Download: author/publisher version (errratum included). Deposit/Metadata: HAL-lirmm-01398338. Citation: BibTeX.
Un matroïde - mot dérivé de ''matrice'' - est une structure combinatoire qui peut être définie en retenant les principales propriétés ensemblistes de la dépendance linéaire dans les espaces vectoriels. Ainsi, lorsqu'il est associé à un ensemble fini de points, il capture les relations d'incidence (alignement, coplanarité, etc.) entre ces points. Un matroïde orienté est une structure combinatoire proche qui capture - en plus, dans ce cas - les relations de convexité entre ces points, en prenant cette fois en compte les signes dans les relations de dépendance linéaire. Il correspond en toute généralité à un objet topologique : un arrangement de pseudosphères. Les matroïdes et les matroïdes orientés satisfont de nombreuses axiomatiques équivalentes, possèdent une notion fondamentale de dualité, et fournissent un cadre adéquat pour des notions classiques variées (en théorie des graphes, en optimisation discrète, en géométrie, etc.), ce qui leur confère un caractère très naturel.
Computing the fully optimal spanning tree of an ordered bipolar directed graph. With Michel Las Vergnas (Rip). Discrete Mathematics, Volume 347, Issue 5, #113895 (2024). Note. Complement of [J13], et particular/adapted case of [Z02].
Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-04387449. Citation: BibTeX.
It was previously shown by the authors that a directed graph on a linearly ordered set of edges (ordered graph) with adjacent unique source and sink (bipolar digraph) has a unique fully optimal spanning tree, that satisfies a simple criterion on fundamental cycle/cocycle directions. This result is related to a strengthening of the notion of optimality in linear programming. Furthermore, this result yields, for any ordered graph, a canonical bijection between bipolar orientations and spanning trees with internal activity 1 and external activity 0 in the sense of the Tutte polynomial. This bijection can be extended to all orientations and all spanning trees, yielding the active bijection, presented for graphs in other papers. In this paper, we specifically address the problem of the computation of the fully optimal spanning tree of an ordered bipolar digraph. In contrast with the inverse mapping, built by a straightforward single pass over the edge set, the direct computation is not easy and had previously been left aside. We give two independent constructions. The first one is a deletion/contraction recursion, involving an exponential number of minors. It is structurally significant but it is efficient only for building the whole bijection (i.e., all images) at once. The second one is more complicated and is the main contribution of the paper. It involves just one minor for each edge of the resulting spanning tree, and it is a translation and an adaptation to the case of graphs, in terms of weighted cocycles, of a general geometric linear programming type algorithm, which allows for a polynomial time complexity. Keywords: Bipolar directed graph, Spanning tree, Computational complexity, Linear programming, Active bijection, Tutte polynomial
On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids. Discrete Mathematics, 345 (7), #112796 (2022). Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-03269872. Citation: BibTeX.
We introduce the active partition of the ground set of an oriented matroid perspective (or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set. Dedicated to Michel Las Vergnas' spirit. Keywords: Tutte polynomial, Matroid perspective, Oriented matroid perspective, Strong map, Quotient, Morphism, Digraph homomorphism
Complete graph drawings up to triangle mutations. Discrete and Computational Geometry, 67, pp.985-1022 (2022). Note. completed journal version of [C03]
Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-03371693. Citation: BibTeX.
The main result of the paper can be stated in the following way: a complete graph drawing in the sphere, where two edges have at most one common point, which is either a crossing or a common endpoint, and no three edges share a crossing, is determined by the circular ordering of edges at each vertex, or equivalently by the set of pairs of edges that cross, up to homeomorphism and a sequence of triangle mutations. A triangle mutation (or switch, or flip) consists in passing an edge across the intersection of two other edges, assuming the three edges cross each other and the region delimited by the three edges has an empty intersection with the drawing. Equivalently, the result holds for a drawing in the plane assuming the drawing is given with a pair of edges indicating where the unbounded region is. The proof is constructive, based on an inductive algorithm that adds vertices and their incident edges one by one (actually yielding an extra property for the sequence of triangle mutations). This result generalizes Ringel's theorem on uniform pseudoline arrangements (or rank 3 uniform oriented matroids) to complete graph drawings. We also apply this result to plane projections (or visualizations) of a geometric spatial complete graph, in terms of the rank 4 uniform oriented matroid defined by its vertices. Independently, we prove that, for a complete graph drawing, the set of pairs of edges that cross determine, by first order logic formulas, the circular ordering of edges at each vertex, as well as further information. Keywords: Graph drawing, Complete graph, Triangle flip, Mutation, Algorithm, Pseudoline arrangement, Ringel's theorem, Oriented matroid, Logical relations
The active bijection for graphs. With Michel Las Vergnas (Rip). Advances in Applied Mathematics, 104, pp.165-236 (2019) Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-01996135 . Citation: BibTeX.
The active bijection forms a package of results studied by the authors in a series of papers in oriented matroids. The present paper is intended to state the main results in the particular case, and more widespread language, of graphs. We study fundamental properties of (directed) graphs on a linearly ordered set of edges. The central result is that, for a directed graph on a linearly ordered set of edges, we determine in a canonical way one particular spanning tree, which we call the active spanning tree and which has important properties. For any graph on a linearly ordered set of edges, this yields a surjective mapping from orientations onto spanning trees, which preserves activities (for orientations in the sense of Las Vergnas, for spanning trees in the sense of Tutte), as well as some partitions (or filtrations) of the edge set associated with orientations and spanning trees. This yields a canonical bijection between classes of orientations and spanning trees, as well as a refined bijection between all orientations and edge subsets, containing various notable bijections, for instance: between orientations in which smallest edges of cycles and cocycles have a fixed orientation and spanning trees; or between acyclic orientations and no-broken-circuit subsets. Several constructions of independent interest are involved. The basic case concerns bipolar orientations, which are in bijection with their fully optimal spanning trees, as proved in a previous paper. We give a canonical decomposition of a directed graph on a linearly ordered set of edges into acyclic/cyclic bipolar directed graphs. Considering all orientations of a graph, we obtain an expression of the Tutte polynomial in terms of products of beta invariants of minors, an important partition of the set of orientations into activity classes, and a simple expression of the Tutte polynomial using four orientation-activity parameters. We derive a similar decomposition theorem for spanning trees. We also provide a general deletion/contraction framework for these bijections and relatives.
On the number of circuit–cocircuit reversal classes of an oriented matroid. With Chi Ho Yuen. Discrete Mathematics, 342 (4), pp.1056-1059 (2019). Note. Complementary converse theorem for [J06] and new proof based on active partitions from [J02][J13].
Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-01996159 . Citation: BibTeX.
The first author introduced the circuit–cocircuit reversal system of an oriented matroid, and showed that when the underlying matroid is regular, the cardinalities of such system and its variations are equal to special evaluations of the Tutte polynomial (e.g., the total number of circuit–cocircuit reversal classes equals t(M;1,1), the number of bases of the matroid). By relating these classes to activity classes studied by the first author and Las Vergnas, we give an alternative proof of the above results and a proof of the converse statements that these equalities fail whenever the underlying matroid is not regular. Hence we extend the above results to an equivalence of matroidal properties, thereby giving a new characterization of regular matroids. Keywords: Regular matroid, Oriented matroid, Tutte polynomial, Circuit reorientation, Reversal system, Active partition, Activity classes
Computation with No Memory, and Rearrangeable Multicast Networks. With Serge Burckel, Emmanuel Thomé. Discrete Mathematics and Theoretical Computer Science, Vol. 16 no. 1 (1), pp.121-142 (2014). Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00959964. Citation: BibTeX.
We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time, hence using no extra memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n-1 component modifications, that is by a program of length 2n-1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinment of the first, described when |S| is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g Z/sZ for any integer s), we build a program with maximal length 2n-1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z/2Z. Keywords: matrix decomposition, modular arithmetic, linear mapping, combinatorial logic, boolean mapping, bijective mapping, mapping computation, memory optimization, multistage interconnection network, multicast rearrangeability, butterfly
Practical and Efficient Circle Graph Recognition. With Christophe Paul, Marc Tedder, Derek Corneil. Algorithmica, 69 (4), pp.759-788 (2014). Note. uses [J09] (companion paper)
Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00805194. Citation: BibTeX.
Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is O(n + m) times the inverse Ackermann function, α(n + m), whose value is smaller than 4 for any practical graph. The algorithm is based on a new in- cremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The algorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper. Keywords: Circle graph, Graph-labelled tree, Split decomposition, Almost linear time algorithm
Practical and Efficient Split Decomposition via Graph-Labelled Trees. With Christophe Paul, Marc Tedder, Derek Corneil. Algorithmica, 69 (4), pp.789-843 (2014). Note. uses the structure from [J08], deeply builds on it, and is used in [J10] (companion paper)
Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00805193. Citation: BibTeX.
Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decompo- sition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time O(n + m)α(n + m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algorithms 36(2):205-240, 2000), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation. Keywords: Split decomposition, Graph-labelled tree, Almost linear time algorithm
Split Decomposition and Graph-Labelled Trees: Characterizations and Fully-Dynamic Algorithms for Totally Decomposable Graphs. With Christophe Paul. Discrete Applied Mathematics, 160 (6), pp.708-733 (2012). Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00783420. Citation: BibTeX.
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give strutural and incremental characterizations, leading to optimal fullydynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs. The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs. Keywords: Split decomposition, Graph-labelled tree, Fully dynamic algorithm, Distance hereditary graph, Cograph, 3-leaf power graph
The present paper is the first in a series of four introducing a mapping from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions - one in terms of activities of reorientations, and the other in terms of activities of bases - of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial. We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection. Keywords: hyperplane arrangement, matroid, oriented matroid, Tutte polynomial, orientation activity, basis activity, acyclic orientation, bipolar orientation, bounded region, bijection, linear programming, optimal basis
Circuit-Cocircuit Reversing Systems in Regular Matroids. Annals of Combinatorics, 12 (2), pp.171-182 (2008). (Special issue Workshop on Tutte polynomials, Barcelona 2005) Note. extends the main result of [J05] to regular oriented matroids; see [J12] for a converse characterization
Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00324552. Citation: BibTeX.
We consider that two orientations of a regular matroid are equivalent if one can be obtained from the other by successive reorientations of positive circuits and/or positive cocircuits. We study the inductive deletion-contraction structure of these equivalence classes in the set of orientations, and we enumerate these classes as evaluations of the Tutte polynomial. This generalizes results in digraphs from a previous paper. Keywords: Regular matroid, Oriented matroid, Duality, Tutte polynomial, Circuit reorientation, Reversal system
Enumerating Degree Sequences in Digraphs and a Cycle-Cocycle Reversing System. European Journal of Combinatorics, 28 (4), pp.1351-1366 (2007). Note. see [J06][J12] for extensions to regular oriented matroids
Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00154515. Citation: BibTeX.
We give some new enumerations of indegree sequences of orientations of a graph using the Tutte polynomial. Then we introduce some discrete dynamical systems in digraphs consisting in reversing cycles, cocycles, or both, which extend the edge firing game (reversing sinks) by considering all orientations (reversing cocycles) and by introducing duality (reversing cycles). We show that indegree sequences can represent the configurations of these systems, and we enumerate equivalence classes of these systems. In particular, concerning the cycle-cocyle reversing system, we show that its configurations are in bijection with indegree sequences of orientations having a given vertex (quasi-sink of the system) reachable from any other. We also briefly discuss its generalization to oriented matroids, and relate structural and enumerative properties of its configurations to those of the sandpile model or chip firing game. Keywords: Directed graph, degree sequence, cycle reversal, reversal system, Tutte polynomial, duality, discrete dynamical system, edge firing game, chip firing game, sandpile model
On the evaluation at (j,j2) of the Tutte polynomial of a ternary matroid. With Michel Las Vergnas. Journal of Algebraic Combinatorics, 25 (1), pp.1-6 (2007) Download: author/publisher version. Deposit/Metadata: HAL-lirmm-00154516. Citation: BibTeX.
F. Jaeger has shown that up to a ± sign the evaluation at (j,j2) of the Tutte polynomial of a ternary matroid can be expressed in terms of the dimension of the bicycle space of a representation over GF(3). We give a short algebraic proof of this result, which moreover yields the exact value of ±, a problem left open in Jaeger's paper. It follows that the computation of t(j,j2) is of polynomial complexity for a ternary matroid. Keywords: matroid, ternary matroid, graph, Tutte polynomial, knot theory, Jones polynomial, computational complexity
The active bijection between regions and simplices in supersolvable arrangements of hyperplanes. With Michel Las Vergnas. The Electronic Journal of Combinatorics, 11 (2), #R30 (2006). (Stanley Festschrift) Download: author/publisher version. Deposit/Metadata: HAL-lirmm-00154517. Citation: BibTeX.
Comparing two expressions of the Tutte polynomial of an ordered oriented matroid yields a remarkable numerical relation between the numbers of reorientations and bases with given activities. A natural activity preserving reorientation-to-basis mapping compatible with this relation is described in a series of papers by the present authors. This mapping, equivalent to a bijection between regions and no broken circuit subsets, provides a bijective version of several enumerative results due to Stanley, Winder, Zaslavsky, and Las Vergnas, expressing the number of acyclic orientations in graphs, or the number of regions in real arrangements of hyperplanes or pseudohyperplanes (i.e. oriented matroids), as evaluations of the Tutte polynomial. In the present paper, we consider in detail the supersolvable case - a notion introduced by Stanley - in the context of arrangements of hyperplanes. For linear orderings compatible with the supersolvable structure, special properties are available, yielding constructions significantly simpler than those in the general case. As an application, we completely carry out the computation of the active bijection for the Coxeter arrangements An and Bn. It turns out that in both cases the active bijection is closely related to a classical bijection between permutations and increasing trees. Keywords: Hyperplane arrangement, matroid, oriented matroid, supersolvable, chordal graph, triangulated graph, Tutte polynomial, basis, reorientation, region, activity, no broken circuit, Coxeter arrangement, braid arrangement, hyperoctahedral arrangement, bijection, permutation, increasing tree
Activity preserving bijections between spanning trees and orientations in graphs. With Michel Las Vergnas. Discrete Mathematics, 298 (1-3), pp.169-188 (2005). (Special issue FPSAC 2002) Download: author/publisher version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00154519. Citation: BibTeX.
The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink. Keywords: matroid, Tutte polynomial, bijection, sink, algorithm, graph, spanning tree, activity, directed graph, acyclic orientation, source, oriented matroid
Bases, reorientations, and linear programming, in uniform and rank 3 oriented matroids. With Michel Las Vergnas. Advances in Applied Mathematics 32, 212--238 (2004). (Special issue Workshop on Tutte polynomials, Barcelona 2001) Complements. Errata.
Download: author/publisher version (errata file added). Publisher site: here. Citation: BibTeX.
Oriented matroid; Matroid; Tutte polynomial; Basis; Basis activity; Orientation; Acyclic orientation; Pseudoline; Pseudoline arrangement; Linear programming; Bijective proof
A Combinatorial Method for 3D Landmark-based Morphometry: Application to the Study of Coronal Craniosynostosis. With Kevin Sol, Gérard Subsol. Proceedings MICCAI: Medical Image Computing and Computer-Assisted Intervention, Oct 2012, Nice, France. LNCS, Volume 7512, pp.533-541 (2012) Complements.
Poster: pdf.
Video:
wmv.
Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-00739362. Citation: BibTeX.
We present a new method to analyze, classify and characterize 3D landmark-based shapes. It is based on a framework provided by oriented matroid theory, that is on a combinatorial encoding of convexity properties. We apply this method to a set of skull shapes presenting various types of coronal craniosynostosis.
Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices. With Kevin Sol, Gérard Subsol. Proceedings CCCG 2011 - 23rd Canadian Conference on Computational Geometry, Aug 2011, Toronto, Canada (2011) Note. Version without proofs of [V02]
Download: author version. Deposit/Metadata: HAL-lirmm-00741936. Citation: BibTeX.
We address the problem of testing when orderings on coordinates of n points in an (n-1)-dimensional affine space, one ordering for each coordinate, suffice to determine if these points are the vertices of a simplex (i.e. are affinely independent), and the orientation of this simplex, independently of the real values of the coordinates. In other words, we want to know when the sign (or the non-nullity) of the determinant of a matrix whose columns correspond to affine points is determined by orderings given on the values on each row. We completely solve the problem in dimensions 2 and 3, providing a direct combinatorial characterization, together with a formal calculus method, that can be seen also as a decision algorithm, which relies on testing the existence of a suitable inductive cofactor expansion of the determinant. We conjecture that the method we use generalizes in higher dimensions. The motivation for this work is to be part of a study on how oriented matroids encode shapes of 3-dimensional objects, with applications in particular to the analysis of anatomical data for physical anthropology and clinical research. Keywords: Simplex orientation, determinant sign, chirotope, coordinate ordering, combinatorial algorithm, formal calculus, oriented matroid, 3D model
A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements. With Michel Las Vergnas. Proceedings EuroComb'09: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. Electronic Notes in Discrete Mathematics, 34, pp.307-311 (2009) Download: author version. Deposit/Metadata: HAL-lirmm-00395075. Citation: BibTeX.
The fully optimal basis of a bounded acyclic oriented matroid on a linearly ordered set has been defined and studied by the present authors in a series of papers, dealing with graphs, hyperplane arrangements, and oriented matroids (in order of increasing generality). This notion provides a bijection between bipolar orientations and uniactive internal spanning trees in a graph resp. bounded regions and uniactive internal bases in a hyperplane arrangement or an oriented matroid (in the sense of Tutte activities). This bijection is the basic case of a general activity preserving bijection between reorientations and subsets of an oriented matroid, called the active bijection, providing bijective versions of various classical enumerative results. Fully optimal bases can be considered as a strenghtening of optimal bases from linear programming, with a simple combinatorial definition. Our first construction used this purely combinatorial characterization, providing directly an algorithm to compute in fact the reverse bijection. A new definition uses a direct construction in terms of a linear programming. The fully optimal basis optimizes a sequence of nested faces with respect to a sequence of objective functions (whereas an optimal basis in the usual sense optimizes one vertex with respect to one objective function). This note presents this construction in terms of graphs and linear algebra.
Mapping computation with no memory. With Serge Burckel, Emmanuel Thomé. Proceedings Unconventional Computation 2009 (Açores). LNCS 5715, pp. 85-97 (2009) Note. Obsolete preliminary version of [J11].
In Situ Design of Register Operations. With Serge Burckel. Proceedings ISVLSI: IEEE Symposium on Very-Large-Scale Integration, LIRMM, Apr 2008, Montpellier, France. Trends in VLSI Technology and Design, IEEE, pp.451-454 (2008) Note. Application of theoretical results detailed in [J11], for which a patent was filed (see in the page below).
Download: author version. Deposit/Metadata: HAL-lirmm-00287659. Citation: BibTeX.
We present methods to design programs or electronic circuits, for performing any operation on K registers of any sizes in a processor, in such a way that one uses no other working memory (such as other registers or external memories). In this way, any operation is performed with at most 4K-3 assignments of these registers, or 2K-1 when the operation is linear or bijective. Keywords: Register operation, Boolean mapping, Program design, Circuit design, Memory optimization, Processor optimization
Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids. With Michel Las Vergnas. Proceedings EuroComb'07: European Conference on Combinatorics, Graph Theory and Applications, Sep 2007, Sevilla. Electronic Notes in Discrete Mathematics 29, pp.365-371 (2007). Note. Erratum to be added (missing \bar\beta in Corollary 3)
Complements. Slides of the talk
Download: author version. Deposit/Metadata: HAL-lirmm-00154521. Citation: BibTeX.
In this note, we present the main results of a series of forthcoming papers, dealing with bijective generalizations of some counting formulas. New intrinsic constructions in oriented matroids on a linearly ordered set of elements establish notably structural links between counting regions and linear programming. We introduce 'fully optimal bases', which have a simple combinatorial characterization, and strengthen the well-known optimal bases of linear programming. Our main result is that every bounded region of an ordered hyperplane arrangement, or ordered oriented matroid, has a unique fully optimal basis, providing the 'active bijection' between bounded regions and uniactive internal bases. The active bijection is extended to an activity preserving mapping between all reorientations and all bases of an ordered oriented matroid. It gives a bijective interpretation of the equality of two expressions for the Tutte polynomial, as well as a new expression of this polynomial in terms of beta invariants of minors. There are several refinements, such as an activity preserving bijection between regions (acyclic reorientations) and no-broken-circuit subsets, and others in terms of hyperplane arrangements, graphs, and permutations. Keywords: oriented matroid, hyperplane arrangement, graph, Tutte polynomial, linear programming, optimal basis, bijection, reorientation, basis, region, no broken circuit
Dynamic Distance Hereditary Graphs Using Split Decomposition. With Christophe Paul. Proceedings ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.41-51 (2007). Note. Obsolete conference paper, see the complete journal version [J08]
Complements. Slides of the talk
Download: author version. Deposit/Metadata: HAL-lirmm-00189506. Citation: BibTeX.
The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity O(d), where d is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.
Complete graph drawings up to triangle mutations. Proceedings WG'05: International Workshop on Graph-Theoretic Concepts in Computer Science, Metz, France, 2005. LNCS 3787, pp139-150 (2005) Note. Short obsolete conference paper with theorem statement and outline of the proof. See the complete journal version [J14].
Complements. Slides of a more general talk at CSL 2006 (on pseudolines, axiomatizations, graph drawings, triangle mutations, at Computer Science Logic 2006)
Download: author version. Citation: BibTeX.
On a natural correspondence between bases and reorientations, related to the Tutte polynomial and linear programming, in graphs, hyperplane arrangements, and oriented matroids. With Michel Las Vergnas. Proceedings FPSAC 2003 (Formal Power Series and Algebraic Combinatorics), Linköping, Sweden (2003) Complements. slides of the talk
Download: author/publisher version (errata included). Citation: BibTeX.
A comparison of two expressions of the Tutte polynomial of an ordered oriented matroid yields remarkable numerical relations between the numbers of bases and reorientations with given activities. We address here the bijection problem for these relations, by constructing a natural activity preserving correspondence with suitable multiplicities between bases and reorientations, called the canonical active (basis-reorientation) correspondence. A decomposition of activities is used, reducing the problem to situations with one activity equal to 1 and the other equal to 0. This decomposition is closely related to a new expression of the Tutte polynomial in terms of beta invariants of minors. This canonical active correspondence has strong duality properties, and can be constructed inductively using minors with respect to the greatest element. Furthermore, it can be refined into an active bijection between all subsets of elements, inducing an active bijection between faces of the NBC complex of the matroid and regions of the oriented matroid. In the graphical case, we get active bijections between spanning trees and activity classes of orientations, resp. acyclic orientations with a unique sink at a given vertex, resp. acyclic orientations with adjacent unique source and unique sink at given vertices. For the regions of an hyperplane arrangement, we get an active bijection between certain simplices and activity classes of regions. Its restriction to simplices with (1,0)-activities and bounded regions is a bijection. If the hyperplanes are in general position, the bijection can be obtained by maximizing or minimizing a same linear function over all bounded regions. In general, we get extensions of linear and oriented matroid programming: each reorientation is decomposed into bounded regions, and for each bounded region, instead of optimizing a face with respect to one objective function, we optimize a sequence of nested faces with respect to a sequence of objective functions.
Activity preserving bijections between spanning trees and orientations in graphs. With Michel Las Vergnas. Proceedings FPSAC 2002 (Formal Power Series and Algebraic Combinatorics), Melbourne, Australia (2002) Note. Obsolete truncated version of [J02]
On counting orientations for graph homomorphisms and for dually embedded graphs using the Tutte polynomial of matroid perspectives. Extended abstract for ICGT 2022 - 11th International Colloquium on Graph Theory and Combinatorics, Jul 2022, Montpellier, France. 4 pages. Note. see [E04] for a completed journal version
Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-03868791. Citation: BibTeX.
An (oriented) matroid perspective (or morphism, or strong map, or quotient) is an ordered pair of (oriented) matroids satisfying some structural relationship. In this presentation, we will focus on the case of graphs, where two notable types of perspectives can be considered: graph homomorphisms, and dually embedded graphs on a surface. The Tutte polynomial of such a perspective is a classical polynomial (also called Las Vergnas polynomial in the case of dually embedded graphs), whose coefficients and (some) evaluations are known to count pairs of orientations of certain types. In this presentation, we show how coefficients and (other) evaluations of the polynomial also count pairs of orientations of certain types where some edge orientations are fixed, as well as some equivalence classes of pairs of orientations of certain types. These properties appear when the edge set is linearly ordered. Dedicated to the memories of Claude Berge and Michel Las Vergnas, as Claude Berge used to be the thesis advisor of Michel Las Vergnas who used to be my own thesis advisor. Keywords: Graph orientations, Graph embedding, Graph homomorphism, Matroid perspective, Strong map, Matroid morphism, Oriented matroid, Tutte polynomial, Active partition, Activity classes
Recognition of dynamic circle graphs. With Christophe Crespelle, Christophe Paul. Extended abstract for ICGT 2014: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France (2014). Note. A complete journal version has been in standby since 2015 [V01]
Download: author version. Publisher site: here. Deposit/Metadata: HAL-lirmm-01178215v1. Citation: BibTeX.
We give quadratic (optimal) fully-dynamic algorithm for circle graph recognition with respect to vertex insertion/deletion.
A new 3D morphometric method based on a combinatorial encoding of 3D point confguration: application to skull anatomy for clinical research and physical antropology. With K. Sol, G. Subsol, Y.Heuzé, J. Richtsmeier, J. Braga, F. Thackeray. Poster. 80th annual meeting of the American Association of physical antropologists (Minneapolis, USA, April 12-16, 2011). (Abstract: American Journal of Physical Antropology 144 (S52) (2011), 280.) Note. Preliminary works having lead to the OMSMO Software [S02]. Click here for information on this software
Download: poster.
Une nouvelle méthode de morphométrie 3D par codage combinatoire de confgurations de points 3D: application à l'anatomie du crâne.. With K. Sol, G. Subsol, J. Braga, J. Treil. Abstract. 1836èmes Journées de la Societé d'Anthropologie de Paris (26-28 janvier 2011). Note. Publication of an abstract for the conference booklet without further production (as usual in this field). See [P02] instead. See also OMSMO Software [S02]. (A laisser dans la liste ou pas ?)
Download: author version.
Actuellement, l’analyse de la forme 3D des structures anatomiques se fonde sur l’étude des distances ou des angles entre des points de repère (par exemple, les mesures craniométriques) ou de paramètres métriques caractérisant la déformation entre des configurations de points de repère relevés sur plusieurs échantillons (voir la méthode de « morphométrie géométrique »). Or, souvent, les différences significatives (c’est-à-dire qui ne dépendent pas que de la variabilité interindividuelle normale) entre des structures anatomiques ne sont pas métriques mais « structurelles ». Par exemple, dans le cas d’une face prognathe, c’est tout un sous-ensemble de points de repère qui passe devant un autre, de manière groupée et corrélée. Or, ceci n’est pas toujours bien mis en évidence par les variations des coordonnées des points de repères. Ceci suggère d'introduire de nouveaux outils de morphométrie 3D adaptés à cette approche. Nous proposons de modéliser les configurations de points de repère 3D par la théorie des matroïdes orientés, une structure mathématique combinatoire développée depuis une trentaine d'années dans le cadre de recherches théoriques en algèbre linéaire et en théorie des graphes. Les matroïdes orientés permettent de modéliser les positions relatives de points dans l’espace sans tenir compte de leurs distances. Il est alors possible de caractériser directement certaines propriétés géométriques comme la convexité ou l’alignement d’un sous-ensemble de points de repères et de détecter des changements structurels comme le passage d’un point de repère à travers le plan formé par 3 autres. Nous avons commencé à appliquer cette nouvelle méthode à des données 3D de crâne pour des applications en chirurgie maxillo-faciale (en particulier, pour caractériser les classes dentaires) ou en paléoanthropologie. Nous présenterons des résultats préliminaires sur la classification automatique de formes 3D complexes et sur la caractérisation des sous-structures les plus significatives.
Rectangles, integer vectors and hyperplanes of the hypercube. With Ilda da Silva. arXiv:2009.14275 (2020) Note. Publication process in standby. Work in the continuation of the conference talk: "Integer vectors and combinatorial properties of affine dependencies of
±1 vectors over the reals", Symmetry in Finite and Infinite Structures (Conference to celebrate the 70th Anniversary of Peter J. Cameron), Lisbon, July 2017.
Deposit/Metadata: arXiv:2009.14275.
We introduce a family of nonnegative integer vectors - primitive vectors - defining hyperplanes of the real affine cube over Cn:={−1,1}n and study their properties with respect to the rectangles of the cube. As a consequence we give a short proof that, for small dimensions (n≤7), the real affine cube can be recovered from its signed rectangles and its signed cocircuits complementary of its facets and skew-facets.
Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices. With Kevin Sol, Gérard Subsol. arXiv:1602.01641 (2016) Note. Complete version of [C09]
Download: author version. Deposit/Metadata: arXiv:1602.01641. Citation: BibTeX.
Provided n points in an (n − 1)-dimensional affine space, and one ordering of the points for each coordinate, we address the problem of testing whether these orderings determine if the points are the vertices of a simplex (i.e. are affinely independent), regardless of the real values of the coordinates. We also attempt to determine the orientation of this simplex. In other words, given a matrix whose columns correspond to affine points, we want to know when the sign (or the non-nullity) of its determinant is implied by orderings given to each row for the values of the row. We completely solve the problem in dimensions 2 and 3. We provide a direct combinatorial characterization, along with a formal calculus method. It can also be viewed as a decision algorithm, and is based on testing the existence of a suitable inductive cofactor expansion of the determinant. We conjecture that our method generalizes in higher dimensions. This work aims to be part of a study on how oriented matroids encode shapes of 3-dimensional landmark-based objects. Specifically, applications include the analysis of anatomical data for physical anthropology and clinical research. Keywords: simplex orientation, determinant sign, chirotope, coordinate ordering, combinatorial algorithm, formal calculus, oriented matroid, 3D model, 3D landmark-based morphometry
Recognition of dynamic circle graphs. With Christophe Crespelle, Christophe Paul. Note. Preprint not released. The publication process for the complete paper for [P03] has been in standby since 2015 (revision/rewriting to make). (A laisser dans la liste ou pas ?)
A Qualitative Reasoning Model for Software Testing, based on Oriented Matroids. With Spyros Xanthakis. In preparation. Note. Journal version of [L02] (with full theoretical proofs and application complements, possibly split into two papers).
Presentation of the OMSMO Software and application to lemur teeth classification. With Yann Marin, Gérard Subsol, Cyril Bouvier. In preparation. Note. This paper will also present the forthcoming version 1.1 of the software [S02]. Click here for information on the software
The Active Bijection 3 - Construction of fully optimal bases, and elaborations on pseudo/real linear programming . With Michel Las Vergnas (Rip). In preparation. Note. See [J16] for the detailed construction adapted/applied to graphs. See [C08] for a short presentation of the construction in the real case.
The Active Bijection 4 - Deletion/contraction constructions and universality results. With Michel Las Vergnas (Rip). In preparation. Note. See [J13] (Section 6) for the main properties of the deletion/contraction construction in graphs.
OMSMO Software - Oriented Matroids for Shape Modeling. With Boris Albar, Cyril Bouvier. OMSMO Software - version 1.0 (12/2019) Note. Evolution of the software [S01]. Click here for information on this software
L'adresse de ce logiciel en ligne est : https://omsmo.lirmm.fr/. Les matroïdes orientés sont des structures mathématiques qui permettent de décrire les relations d'incidence (alignement, appartenance à un même plan, etc.) et de convexité / concavité dans un ensemble de points de l'espace. De manière générale, ils sont liés à des structures fondamentales et variées dans divers domaines des mathématiques et de l'informatique, ce qui leur confère un caractère très naturel. Ce logiciel consiste à utiliser ces structures pour une application interdisciplinaire. On utilise ici les matroïdes orientés afin de chercher à analyser ou caractériser des formes d'objets 3D définis par des points de repère (obtenus à l'aide d'un scanner à partir d'un squelette par exemple). Brièvement, il s'agit d'oublier les mesures numériques d'un modèle (distances, angles...) utilisées habituellement, et de se focaliser sur l'information discrète qui caractérise sa structure (une liste de bits décrivant la forme d'une certaine façon). Cette approche de la modélisation de formes 2D/3D et de la morphométrie (étude quantitative et qualitative des formes d'objets réels) est nouvelle. La mise en place informatique de cette approche a pour but de classifier/détecter/analyser de façon automatique des types anatomiques/espèces/pathologies en sciences naturelles, et au delà de proposer un nouvel outil pour la reconnaissance informatique de formes d'objets 2D/3D. Le logiciel en ligne est hébergé à Montpellier au LIRMM en vue d’utilisation par des chercheurs internationaux de diverses disciplines : informatique (imagerie 2D/3D, reconnaissance de forme), médecine (imagerie médicale, anatomie, médecine assistée par ordinateur), anthropologie biologique, paléontologie, etc., afin qu'ils obtiennent soit des confirmations mathématiques et formelles de résultats qu'ils connaissaient empiriquement, soit des nouveaux résultats décelés grâce à cette approche nouvelle, soit de nouvelles techniques efficaces et complémentaires des techniques existantes.
Implémentation de calculs pour processeurs. With Serge Burckel, et Université de la Réunion. Brevet. Numéro INPI d'enregistrement national : 07 05152. Date de dépôt : 17/07/2007. Date de publication : 25/03/2011. (French patent registration) Note. Invention based on results presented in [C06] and detailed in [J11].
Complements. Classification internationale : G06F 8/441. Dernière annuité payée : 17/05/2023. Pochaine annuité : 31/07/2024.
Download: extrait de la base INPI au 4 avril 2024.
Correspondance naturelle entre bases et réorientations des matroïdes orientés. Thèse de doctorat de l'Université Bordeaux 1, 2002 (Spécialité Informatique mention Mathématiques Discrètes, 18 décembre 2002). Note. French Ph.D. Thesis. (Thesis supervised by Michel Las Vergnas and cosupervised by Bruno Courcelle.)
Complements. (1) Errata.(2) Récréation (jeu/puzzle sur les arrangements de pseudodroites ne nécéssitant pas de connaissance préalable).
Download: Thesis (without erratum).
L'objet de cette thèse est de définir et d'étudier, de façon intrinsèque et de façon constructive, une application naturelle qui à un matroïde orienté ordonné associe une de ses bases. Pour un matroïde orienté ordonné donné, elle induit une correspondance, déterminée par certaines conditions, entre l'ensemble de ses réorientations et celui de ses bases. Une condition fondamentale à satisfaire est que les activités soient conservées. Les activités d'une base dans un matroïde ordonné, définies par Tutte, sont deux paramètres entiers duaux, de même que les activités d'un matroïde orienté ordonné, définies par Las Vergnas. En très bref, elles situent ces objets par rapport aux bases minimales et maximales pour l'ordre lexicographique. La correspondance est appelée ainsi correspondance active canonique du matroïde orienté ordonné, et constitue une preuve bijective de propriétés énumératives connues du polynôme de Tutte. Une autre condition est qu'elle soit invariante par passage au dual : la dualité est utilisée partout ici de façon essentielle, dans les caractéristiques fondamentales comme dans les algorithmes. La correspondance active canonique a des propriétés géométriques remarquables, et peut-être construite inductivement soit en utilisant les mineurs relativement au plus grand élément, soit en utilisant une décomposition des activités qui réduit le problème aux activités (1,0). En termes de bases, cette décomposition donne une nouvelle expression du polynôme de Tutte utilisant les invariants béta de certains mineurs. En termes de réorientations, cette décomposition conduit à une notion de classes d'activités de réorientations, lesquelles sont en bijection active avec les bases. En outre, cette bijection peut-être raffinée en une bijection active entre tous les sous-ensembles d'éléments, qui induit une bijection active entre les régions du matroïde orienté et les parties sans circuit brisé (circuit moins son plus petit élément) du matroïde (faces du complexe NBC). Dans le cas d'un graphe, on obtient notamment une bijection active entre les arbres couvrants internes (ceux dont les éléments du complémentaires ne sont jamais le plus petit de leur cycle fondamental par rapport à l'arbre) et les orientations acycliques ayant un unique puits fixé ; ainsi qu'une bijection entre arbres couvrants d'activités (1,0) (ceux qui, en plus, sont le plus loin possible de la base minimale) et les orientations acycliques ayant un unique puits et une unique source adjacents fixés. Dans le cas d'un arrangement d'hyperplans, on obtient notamment une bijection active entre les simplexes internes et les classes d'activités de régions, ainsi qu'une bijection entre les simplexes d'activités (1,0) et les régions bornées. Si les hyperplans sont en position générale, cette dernière bijection s'obtient en appliquant le même programme linéaire simultanément à toutes les régions bornées, de chaque côté d'un hyperplan distingué, noyau de la forme linéaire à optimiser. L'application générale revient ainsi à une extension de la version combinatoire dans les matroïdes orientés de la programmation linéaire : d'une part chaque réorientation se décompose en régions bornées dans des mineurs du matroïde orienté et de son dual, et d'autre part pour chaque région bornée, au lieu d'un sommet pour une fonction objective, on optimise une suite de faces emboîtées pour une suite de fonctions objectives. Cette application apparait naturellement dès que l'on considère un ordre total sur les éléments des matroïdes orientés. Elle décrit, intuitivement, un phénomène d'attraction dirigée par l'ordre des éléments, et peut-être appelée application (attr)active des matroïdes orientés ordonnés.
CNRS Researcher (since 2005)