Academic literature on the topic 'Complexes simpliciaux et polytopes'

International audience We study a natural generalization of the noncrossing relation between pairs of elements in $[n]$ to $k$-tuples in $[n]$. We show that the flag simplicial complex on $\binom{[n]}{k}$ induced by this relation is a regular, unimodular and flag triangulation of the order polytope of the poset given by the product $[k] \times [n-k]$ of two chains, and it is the join of a simplex and a sphere (that is, it is a Gorenstein triangulation). This shows the existence of a flag simplicial polytope whose Stanley-Reisner ideal is an initial ideal of the Graßmann-Plücker ideal, while previous constructions of such a polytope did not guaranteed flagness. The simplicial complex and the polytope derived from it naturally reflect the relations between Graßmannians with different parameters, in particular the isomorphism $G_{k,n} \cong G_{n-k,n}$. This simplicial complex is closely related to the weak separability complex introduced by Zelevinsky and Leclerc. Nous étudions une généralisation naturelle de la relation entre les paires d’éléments non-croisés de $[n]$ et les $k$-uplets de $[n]$. Nous montrons que le complexe simplicial de drapeau sur $\binom{[n]}{k}$ induit par cette relation est une triangulation régulière, unimodulaire et de drapeau du polytope d’ordre de l’ensemble partiellement ordonné obtenu par le produit $[k] \times [n-k]$ des deux chaînes, et c’est la jointure d’un simplexe et une sphère (c’est-à-dire qu’elle est une triangulation de Gorenstein). Cela montre l’existence d’un polytope simplicial de drapeau dont l’idéal de Stanley-Reisner est un idéal initial de l’idéal de Graßmann-Plücker, tandis que les constructions précédentes d’un tel polytope ne garantissaient pas la propriété de drapeau. Le complexe simplicial et le polytope qui en découle reflètent naturellement les relations entre les Grassmanniens avec différents paramètres, en particulier l’isomorphisme $G_{k,n} \cong G_{n-k,n}$. Ce complexe simplicial est étroitement lié au complexe de séparabilité faible étudié par Zelevinskyet Leclerc.

The notion of $r$-stackedness for simplicial polytopes was introduced by McMullen and Walkup in 1971 as a generalization of stacked polytopes. In this paper, we define the $r$-stackedness for triangulated homology manifolds and study their basic properties. In addition, we find a new necessary condition for face vectors of triangulated manifolds when all the vertex links are polytopal. Généralisant les polytopes simpliciaux empilés, McMullen et Walkup ont introduit en 1971 la notion de $r$-empilement pour les polytopes simpliciaux. Dans cet article, nous définissons la notion de $r$-empilement pour les variétés homologiques simpliciales et étudions ses propriétés élémentaires. En outre, nous donnons une nouvelle condition pour les $f$-vecteurs des variétés simpliciales lorsque tous les sommets ont un lien polytopal.

International audience The face numbers of simplicial polytopes that approximate $C^1$-convex bodies in the Hausdorff metric is studied. Several structural results about the skeleta of such polytopes are studied and used to derive a lower bound theorem for this class of polytopes. This partially resolves a conjecture made by Kalai in 1994: if a sequence $\{P_n\}_{n=0}^{\infty}$ of simplicial polytopes converges to a $C^1$-convex body in the Hausdorff distance, then the entries of the $g$-vector of $P_n$ converge to infinity. Nous étudions les nombres de faces de polytopes simpliciaux qui se rapprochent de $C^1$-corps convexes dans la métrique Hausdorff. Plusieurs résultats structurels sur le skeleta de ces polytopes sont recherchées et utilisées pour calculer un théorème limite inférieure de cette classe de polytopes. Cela résout partiellement une conjecture formulée par Kalai en 1994: si une suite $\{P_n\}_{n=0}^{\infty}$ de polytopes simpliciaux converge vers une $C^1$-corps convexe dans la distance Hausdorff, puis les entrées du $g$-vecteur de $P_n$ convergent vers l’infini.

The $d$-dimensional simplicial, terminal, and reflexive polytopes with at least $3d-2$ vertices are classified. In particular, it turns out that all of them are smooth Fano polytopes. This improves previous results of Casagrande (2006) and Øbro (2008). Smooth Fano polytopes play a role in algebraic geometry and mathematical physics. This text is an extended abstract of Assarf et al. (2012). Nous classifions les polytopes simpliciaux, terminaux et réflexifs de dimension $d$ avec au moins $3d-2$ sommets. En particulier, tous ces polytopes se trouvent être des polytopes de Fano lisses. Nous améliorons des résultats antérieurs de Casagrande (2006) et d’Øbro (2008). Les polytopes de Fano lisses apparaissent en géométrie algébrique et en physique mathématique. Ce texte est un résumé étendu de Assarf et al. (2012).

International audience Given a graph $G$, the number of nowhere-zero $\mathbb{Z}_q$-flows $\phi _G(q)$ is known to be a polynomial in $q$. We extend the definition of nowhere-zero $\mathbb{Z} _q$-flows to simplicial complexes $\Delta$ of dimension greater than one, and prove the polynomiality of the corresponding function $\phi_{\Delta}(q)$ for certain $q$ and certain subclasses of simplicial complexes. Etant donné un graphe $G$, on est connu que le nombre de $\mathbb{Z}_q$-flots non-nuls $\phi _G(q)$ est un polynôme dans $q$. Nous étendons la définition de $\mathbb{Z} _q$-flots non-nuls pour inclure des complexes simpliciaux de dimension plus grande qu'un, et on montre que le nombre est aussi un polynôme de la fonction correspondante pour certain valeurs de $q$ et de certaines sous-classes de complexes simpliciaux.

International audience We generalize the theory of critical groups from graphs to simplicial complexes. Specifically, given a simplicial complex, we define a family of abelian groups in terms of combinatorial Laplacian operators, generalizing the construction of the critical group of a graph. We show how to realize these critical groups explicitly as cokernels of reduced Laplacians, and prove that they are finite, with orders given by weighted enumerators of simplicial spanning trees. We describe how the critical groups of a complex represent flow along its faces, and sketch another potential interpretation as analogues of Chow groups. Nous généralisons la théorie des groupes critiques des graphes aux complexes simpliciaux. Plus précisément, pour un complexe simplicial, nous définissons une famille de groupes abéliens en termes d'opérateurs de Laplace combinatoires, qui généralise la construction du groupe critique d'un graphe. Nous montrons comment réaliser ces groupes critiques explicitement comme conoyaux des opérateurs de Laplace réduits combinatoires, et montrons qu'ils sont finis. Leurs ordres sont obtenus en comptant (avec des poids) des arbres simpliciaux couvrants. Nous décrivons comment les groupes critiques d'un complexe représentent le flux le long de ses faces, et esquissons une autre interprétation potentielle comme analogues des groupes de Chow.

International audience We present a family of simplicial complexes called \emphmulti-cluster complexes. These complexes generalize the concept of cluster complexes, and extend the notion of multi-associahedra of types ${A}$ and ${B}$ to general finite Coxeter groups. We study combinatorial and geometric properties of these objects and, in particular, provide a simple combinatorial description of the compatibility relation among the set of almost positive roots in the cluster complex. Nous présentons une famille de complexes simpliciaux appelés \emphcomplexes des multi-amas. Ces complexes généralisent le concept de complexes des amas et étendent la notion de multi-associaèdre de type ${A}$ et ${B}$ aux groupes de Coxeter finis. Nous étudions des propriétés combinatoires et géométriques de ces objets et, en particulier nous fournissons une description combinatoire simple de la relation de compatibilité sur l'ensemble des racines presque positives du complexe des amas.

International audience We consider a Hopf algebra of simplicial complexes and provide a cancellation-free formula for its antipode. We then obtain a family of combinatorial Hopf algebras by defining a family of characters on this Hopf algebra. The characters of these Hopf algebras give rise to symmetric functions that encode information about colorings of simplicial complexes and their $f$-vectors. We also use characters to give a generalization of Stanley’s $(-1)$-color theorem. Nous considérons une algèbre de Hopf de complexes simpliciaux et fournissons une formule sans multiplicité pour son antipode. On obtient ensuite une famille d'algèbres de Hopf combinatoires en définissant une famille de caractères sur cette algèbre de Hopf. Les caractères de ces algèbres de Hopf donnent lieu à des fonctions symétriques qui encode de l’information sur les coloriages du complexe simplicial ainsi que son vecteur-$f$. Nousallons également utiliser des caractères pour donner une généralisation du théorème $(-1)$ de Stanley.

International audience We introduce the short toric polynomial associated to a graded Eulerian poset. This polynomial contains the same information as Stanley's pair of toric polynomials, but allows different algebraic manipulations. Stanley's intertwined recurrence may be replaced by a single recurrence, in which the degree of the discarded terms is independent of the rank. A short toric variant of the formula by Bayer and Ehrenborg, expressing the toric h-vector in terms of the cd-index, may be stated in a rank-independent form, and it may be shown using weighted lattice path enumeration and the reflection principle. We use our techniques to derive a formula expressing the toric h-vector of a dual simplicial Eulerian poset in terms of its f-vector. This formula implies Gessel's formula for the toric h-vector of a cube, and may be used to prove that the nonnegativity of the toric h-vector of a simple polytope is a consequence of the Generalized Lower Bound Theorem holding for simplicial polytopes. Nous introduisons le polynôme torique court associé à un ensemble ordonné Eulérien. Ce polynôme contient la même information que le couple de polynômes toriques de Stanley, mais il permet des manipulations algébriques différentes. La récurrence entrecroisée de Stanley peut être remplacée par une seule récurrence dans laquelle le degré des termes écartés est indépendant du rang. La variante torique courte de la formule de Bayer et Ehrenborg, qui exprime le vecteur torique d'un ensemble ordonné Eulérien en termes de son cd-index, est énoncée sous une forme qui ne dépend pas du rang et qui peut être démontrée en utilisant une énumération des chemins pondérés et le principe de réflexion. Nous utilisons nos techniques pour dériver une formule exprimant le vecteur h-torique d'un ensemble ordonné Eulérien dont le dual est simplicial, en termes de son f-vecteur. Cette formule implique la formule de Gessel pour le vecteur h-torique d'un cube, et elle peut être utilisée pour démontrer que la positivité du vecteur h-torique d'un polytope simple est une conséquence du Théorème de la Borne Inférieure Généralisé appliqué aux polytopes simpliciaux.

International audience We present complete simplicial fan realizations of any spherical subword complex of type $A_n$ for $n\leq 3$. This provides complete simplicial fan realizations of simplicial multi-associahedra $\Delta_{2k+4,k}$, whose facets are in correspondence with $k$-triangulations of a convex $(2k+4)$-gon. This solves the first open case of the problem of finding fan realizations where polytopality is not known. The techniques presented in this paper work for all finite Coxeter groups and we hope that they will be useful to construct fans realizing subword complexes in general. In particular, we present fan realizations of two previously unknown cases of subword complexes of type $A_4$, namely the multi-associahedra $\Delta_{9,2}$ and $\Delta_{11,3}$. Nous construisons des éventails simpliciaux complets ayant la combinatoire des complexes de sous-mots de type $A_n$ pour $n\leq 3$. Par conséquent, nous obtenons des constructions d’éventails des multi-associaèdres $\Delta_{2k+4,k}$, dont les facettes correspondent aux $k$-triangulations d’un $(2k+4)$-gone. Cette construction confirme l’existence d’éventails ayant la combinatoire du multi-associaèdres pour une famille dont la polytopalité n’est pas confirmée. Les techniques utilisées fonctionnent pour tous les groupes de Coxeter et nous espérons qu’elles seront utiles afin de construire des éventails réalisant les complexes de sous-mots en général. En particulier, nous présentons des éventails pour deux complexes de sous-mots de type $A_4$ dont l’existence était inconnue: les multi-associaèdres $\Delta_{9,2}$ et $\Delta_{11,3}$.

Cette thèse s'inscrit dans le domaine de la combinatoire algébrique. Certains algorithmes de tri peuvent être décrits par des diagrammes appelés réseaux de tri, et l'exécution de ces algorithmes sur des permutations se traduit alors par des arrangements de courbes sur ces réseaux. Ces arrangements donnent des modèles pour des structures combinatoires classiques : par exemple, le treillis de Tamari, dont les relations de couverture sont les rotations sur les arbres binaires, et qui est un quotient bien connu de l'ordre faible sur les permutations. Les complexes de sous-mots généralisent les réseaux de tris et les arrangements de courbes aux groupes de Coxeter. Ils ont des liens profonds en algèbre et géométrie, notamment dans le calcul de Schubert, l'étude des variétés grassmanniennes et la théorie des algèbres amassées. Cette thèse s'intéresse aux structures de treillis sur certains complexes de sous-mots, généralisant les treillis de Tamari. Plus précisément, elle étudie la relation définie par les extensions linéaires des facettes d'un complexe de sous-mot. Dans un premier lieu, nous nous intéressons aux complexes de sous-mots définis sur un mot triangulaire du groupe symétrique, que nous représentons par des arrangements de tuyaux triangulaires. Nous prouvons alors que cette relation définit un quotient de treillis d'un intervalle de l'ordre faible ; par ailleurs, nous pouvons également utiliser cette relation pour définir un morphisme de treillis de cet intervalle au graphe des flips du complexe de sous-mots restreint à certaines de ses facettes. Dans un second lieu, nous étendons notre étude aux complexes de sous-mots définis sur les mots alternants du groupe symétrique. Nous montrons que cette même relation définit également un quotient de treillis ; en revanche, le morphisme associé n'a plus pour image le graphe des flips, mais le squelette du polyhèdre de brique, un objet défini sur les complexes de sous-mots pour étudier des réalisations du multi-associahèdre. Enfin, nous discutons des possibles extensions de ces résultats aux groupes de Coxeter finis, ainsi que de leurs applications pour généraliser certains objets définis en type A comme les treillis de nu-Tamari
This thesis comes within the scope of algebraic combinatorics. Some sorting algorithms can be described by diagrams called sorting networks, and the execution of the algorithms on input permutations translates to arrangements of curves on the networks. These arrangements modelize some classical combinatorial structures: for example, the Tamari lattice, whose cover relations are the rotations on binary trees, and which is a well-known quotient of the weak order on permutations. Subword complexes generalize sorting network and arrangements of curves to Coxeter groups. They have deep connections in algebra and geometry, in particular in Schubert calculus, in the study of grassmannian varieties, and in the theory of cluster algebras. This thesis focuses on lattice structures on some subword complexes, generalizing Tamari lattices. More precisely, it studies the relation defined by linear extensions of the facets of a subword complex. At first we focus on subword complexes defined on a triangular word of the symmetric group, which we represent with triangular pipe dreams. We prove that this relation defines a lattice quotient of a weak order interval; moreover, we can also use this relation to define a lattice morphism from this interval to the restriction of the flip graph of the subword complex to some of its facets. Secondly, we extent our study to subword complexes defined on alternating words of the symmetric group. We prove that this same relation also defines a lattice quotient; however, the image of the associated morphism is no longer the flip graph, but the skeleton of the brick polyhedron, an object defines on subword complexes to study realizations of the multiassociahedron. Finally, we discuss possible extensions of these results to finite Coxeter groups, as well as their applications to generalize some objects defined in type A such as nu-Tamari lattices

La résolution efficace de certaines questions de géométrie algorithmique, par exemple les calculs de visibilité ou l'approximation de forme, soulève de nouvelles questions de géométrie des droites, domaine classique dont l'origine remonte à la seconde moitié du 19e siècle. Ce mémoire s'inscrit dans ce cadre, et étudie les nombres de Helly de certains ensembles de droites, un indice reliée à certains théorèmes de la base apparaissant en optimimisation combinatoire. Formellement, le nombre de Helly d'une famille d'ensembles d'intersection vide est le cardinal de sa plus petite sous-famille d'intersection vide et minimale pour l'inclusion relativement à cette propriété. En 1957, Ludwig Danzer a formulé la conjecture que pour tout $d \ge 2$ il existe une constante $h_d$ telle que pour toute famille $\{B_1, \ldots, B_n\}$ de boules deux à deux disjointes et de même rayon, le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $h_d$; ici, $T(B_i)$ désigne l'ensemble des droites coupant $B_i$. Danzer a, de plus, spéculé que la constante $h_d$ (minimale) croît strictement avec $d$. Nous prouvons que de telles constantes existent, et que $h_d$ est au moins $2d-1$ et au plus $4d-1$ pour tout $d \ge 2$. Cela prouve la première conjecture et étaye la seconde. Nous introduisons, pour étudier les conjectures de Danzer, un analogue local du nombre de Helly que nous appellons nombre d'épinglement et qui se rattache à la notion d'immobilisation étudiée en robotique. Nous montrons que le nombre d'épinglement est borné pour toute famille (suffisament générique) de polyèdres ou d'ovaloides de $R^3$, deux cas où les nombres de Helly peuvent être arbitrairement grands. Un théorème de Tverberg énonce que si $\{B_1, \ldots, B_n\}$ est une famille de convexes du plan disjoints et congruents par translation alors le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $5$. Quoique relativement différentes, notre preuve et celle de Tverberg exploitent toutes deux le fait que toute intersection d'au moins deux $T(B_i)$ a un nombre borné de composantes connexes, chacune contractile. Par des considérations sur l'homologie de projections de complexes et d'ensembles simpliciaux, nous unifions ces deux preuves et montrons que cette condition topologique suffit à établir une borne explicite sur le nombre de Helly.

Cette thèse est composée de deux parties. La première partie utilise l’analyse stochastique pour fournir des bornes pour la probabilité de surcharge de différents systèmes grâce aux inégalités de concentration. Bien qu’ils soient généraux, nous appliquons ces résultats à des réseaux sans-fil réels tels que le WiMax et le traffic utilisateur multi-classe dans un système OFDMA. Dans la seconde partie, nous trouvons des liens entre la topologie de la couverture dans un réseau de capteur et celle du complexe simplicial correspondant. Cette analogie met en valeur de nouvelles facettes des certains objets mathématiques comme les nombres de Betti, le nombre de k-simplexes, et la caractéristique d’Euler. Puis, nous utilisons conjointement la topologie algébrique et l’analyse stochastique, en considérant que les positions des capteurs sont une réalisation d’un processus ponctuel de Poisson. Nous en déduisons les statistiques du nombre de k-simplexe et de la caractéristique d’Euler, ainsi que des bornes supérieures pour la distribution des nombres de Betti, le tout en d dimen- sions. Nous démontrons aussi que le nombre de k-simplexes converge vers une distribution Gaussienne quand la densité de capteurs tend vers l’infini à une vitesse de convergence connue. Enfin, nous nous limitons au cas unidimensionnel. Dans ce cas, le problème devient équivalent à résoudre une file M/M/1/1 préemptive. Nous obtenons ainsi des résultats analytiques pour des quantités telles que la distribution du nombre de composantes connexes et la probabilité de couverture totale
This thesis has two main parts. Part I uses stochastic anlysis to provide bounds for the overload probability of different systems thanks to concentration inequalities. Although the results are general, we apply them to real wireless network systems such as WiMax and mutliclass user traffic in an OFDMA system. In part I I, we find more connections between the topology of the coverage of a sensor network and the topology of its corresponding simplicial complex. These connections highlight new aspects of Betti numbers, the number of k-simplices, and Euler characteristic. Then, we use algebraic topology in conjunction with stochastic analysis, after assuming that the positions of the sensors are points of a Point point process. As a consequence we obtain, in d dimensions, the statistics of the number of k-simplices and of Euler characteristic, as well as upper bounds for the distribution of Betti numbers. We also prove that the number of k-simplices tends to a Gaussian distribution as the density of sensors grows, and we specify the convergence rate. Finally, we restrict ourselves to one dimension. In this case, the problem becomes equivalent to solving a M/M/1/1 preemptive queue. We obtain analytical results for quantites such as the distribution of the number of connected components and the probability of complete coverage

Cette thèse est composée de deux parties. La première partie utilise l’analyse stochastique pour fournir des bornes pour la probabilité de surcharge de différents systèmes grâce aux inégalités de concentration. Bien qu’ils soient généraux, nous appliquons ces résultats à des réseaux sans-fil réels tels que le WiMax et le traffic utilisateur multi-classe dans un système OFDMA. Dans la seconde partie, nous trouvons des liens entre la topologie de la couverture dans un réseau de capteur et celle du complexe simplicial correspondant. Cette analogie met en valeur de nouvelles facettes des certains objets mathématiques comme les nombres de Betti, le nombre de k-simplexes, et la caractéristique d’Euler. Puis, nous utilisons conjointement la topologie algébrique et l’analyse stochastique, en considérant que les positions des capteurs sont une réalisation d’un processus ponctuel de Poisson. Nous en déduisons les statistiques du nombre de k-simplexe et de la caractéristique d’Euler, ainsi que des bornes supérieures pour la distribution des nombres de Betti, le tout en d dimen- sions. Nous démontrons aussi que le nombre de k-simplexes converge vers une distribution Gaussienne quand la densité de capteurs tend vers l’infini à une vitesse de convergence connue. Enfin, nous nous limitons au cas unidimensionnel. Dans ce cas, le problème devient équivalent à résoudre une file M/M/1/1 préemptive. Nous obtenons ainsi des résultats analytiques pour des quantités telles que la distribution du nombre de composantes connexes et la probabilité de couverture totale
This thesis has two main parts. Part I uses stochastic anlysis to provide bounds for the overload probability of different systems thanks to concentration inequalities. Although the results are general, we apply them to real wireless network systems such as WiMax and mutliclass user traffic in an OFDMA system. In part I I, we find more connections between the topology of the coverage of a sensor network and the topology of its corresponding simplicial complex. These connections highlight new aspects of Betti numbers, the number of k-simplices, and Euler characteristic. Then, we use algebraic topology in conjunction with stochastic analysis, after assuming that the positions of the sensors are points of a Point point process. As a consequence we obtain, in d dimensions, the statistics of the number of k-simplices and of Euler characteristic, as well as upper bounds for the distribution of Betti numbers. We also prove that the number of k-simplices tends to a Gaussian distribution as the density of sensors grows, and we specify the convergence rate. Finally, we restrict ourselves to one dimension. In this case, the problem becomes equivalent to solving a M/M/1/1 preemptive queue. We obtain analytical results for quantites such as the distribution of the number of connected components and the probability of complete coverage

Dans ce travail, nous etudions le cadre de la morphologie math ematique sur les complexes simpliciaux. Complexes simpliciaux sont une structure versatile et largement utilis ee pour repr esenter des donn ees multidimensionnelles, telles que des maillages, qui sont des complexes tridimensionnels, ou des graphes, qui peuvent etre interpr et ees comme des complexes bidimensionnels. La morphologie math ematique est l'un des cadres les plus puissants pour le traitement de l'image, y compris le traitement des structures num eriques, et est largement utilis e pour de nombreuses applications. Toutefois, les op erateurs de morphologie math ematique sur des espaces complexes simpliciaux n'est pas un concept enti erement d evelopp e dans la litt erature. Dans ce travail, nous passons en revue certains op erateurs classiques des complexes simpliciaux sous la lumi ere de la morphologie math ematique, de montrer qu'ils sont des op erateurs de morphologie. Nous d efi nissons certains treillis de base et les op erateurs agissant sur ces treillis : dilatations, erosions, ouvertures, fermetures et fi ltres altern es s equentiels, et aussi leur extension a simplexes pond er es. Cependant, les principales contributions de ce travail sont ce que nous appelions les op erateurs dimensionnels, petites et polyvalents op erateurs qui peuvent etre utilis es pour d efi nir de nouveaux op erateurs sur les complexes simpliciaux, qui garde les propri et es de la morphologie math ematique. Ces op erateurs peuvent egalement etre utilis es pour exprimer pratiquement n'importe quel op erateur dans la litt erature. Nous illustrons les op erateurs d e nis et nous comparons les filtres altern es s equentiels contre ltres d e finis dans la litt erature, o u nos filtres pr esentent de meilleurs r esultats pour l'enl evement du petit, intense bruit des images binaires.

Malgré l’efficacité des réseaux pour représenter les systèmes complexes, de récents travaux ont montré que leur structure limite parfois le pouvoir explicatif des modèles théoriques, puisqu’elle n’encode que des relations par paire. Si une interaction plus complexe existe dans le système représenté, elle est automatiquement réduite à un groupe d’interactions par paire, c’est-à-dire d’ordre un. Il faut alors utiliser des structures qui prennent en compte les interactions d’ordre supérieur. Cependant, qu’elles soient ou non d’ordre supérieur, les interactions entre les éléments d’un système sont rarement explicites dans les jeux de données. C’est notamment le cas des données de présence/absence qui indiquent quelles espèces (animales, végétales ou autres) se retrouvent (ou non) sur un site d’observation sans indiquer les relations entre elles. L’objectif de ce mémoire est alors de développer une technique d’inférence pour dénicher les interactions d’ordre supérieur au sein de données de présence/absence. Ici, deux cadres théoriques sont explorés. Le premier est basé sur la comparaison entre la topologie des données, obtenue grâce à une hypothèse souple, et celle d’un ensemble aléatoire. Le second utilise plutôt les modèles log-linéaire et les tests d’hypothèses pour inférer les interactions une à une jusqu’à l’ordre désiré. Ce cadre a permis d’élaborer plusieurs méthodes d’inférence qui génèrent des complexes simpliciaux (ou des hypergraphes) qui peut être analysés grâce aux outils standards de la science des réseaux en plus de l’homologie. Afin de valider ces méthodes, nous avons développé un modèle génératif de données de présence/absence dans lesquelles les véritables interactions sont connues. Des résultats concrets ont également été obtenus pour des jeux de données réelles. Notamment, à partir de données de présence/absence d’oiseaux nicheurs du Québec, nous avons réussi à inférer des cooccurrences d’ordre deux.
Despite the effectiveness of networks to represent complex systems, recent work has shownthat their structure sometimes limits the explanatory power of the theoretical models, sinceit only encodes dyadic interactions. If a more complex interaction exists in the system, it isautomatically reduced to a group of pairwise interactions that are of the first order. We thusneed to use structures that can take higher-order interactions into account. However, whetherrelationships are of higher order or not is rarely explicit in real data sets. This is the case ofpresence/absence data, that only indicate which species (of animals, plants or others) can befound (or not) on a site without showing the interactions between them.The goal of this project is to develop an inference method to find higher-order interactionswithin presence/absence data. Here, two frameworks are examined. The first one is based onthe comparison of the topology of the data, obtained with a non-restrictive hypothesis, andthe topology of a random ensemble. The second one uses log-linear models and hypothesistesting to infer interactions one by one until the desired order. From this framework, we havedevelopped several inference methods to generate simplicial complexes (or hypergraphs) thatcan be studied with regular tools of network science as well as homology. In order to validatethese methods, we have developed a generative model of presence/absence data in which thetrue interactions are known. Results have also been obtained on real data sets. For instance,from presence/absence data of nesting birds in Québec, we were able to infer co-occurrencesof order two

Grâce à leur résolution et à leur accessibilité toujours meilleures, les capteurs LiDAR sont de plus en plus utilisés pour cartographier les villes. En effet, ces capteurs sont capables de réaliser efficacement des acquisitions à haut résolution, qui peuvent ensuite être utilisées pour produire des reconstructions géométriquement détaillées de scènes complexes. Cependant, une telle reconstruction nécessite d’organiser les données avec une structure de données adaptée, comme des nuages de points ou des maillages. Les nuages de points fournissent une représentation compacte des données, mais leur nature discrète empêche certaines applications telles que la visualisation ou la simulation. Les maillages permettent une représentation continue des surfaces, mais ne sont pas bien adaptés à la représentation d’objets complexes, dont le niveau de détail peut dépasser la résolution de l’acquisition. Pour remédier à ces limitations, nous proposons de reconstruire une géométrie continue uniquement lorsque suffisamment d’informations géométriques sont disponibles. Cela nous amène à créer une reconstruction mêlant triangles, arêtes et points. Nous appelons une telle collection d’objets un complexe simplicial. Dans cette thèse, nous étudions la création de modèles 3D de scènes urbaines géométriquement détaillés, basés sur des complexes simpliciaux. Nous montrons que les complexes simpliciaux sont une alternative appropriée aux maillages. En effet, ils sont rapides à calculer et peuvent être simplifiés tout en conservant une grande fidélité géométrique par rapport aux données d’entrée. Nous soutenons que les complexes simples transmettent de précieuses informations géométriques qui peuvent à leur tour être utilisées pour la sémantisation des nuages de points 3D. Nous pensons également qu’ils peuvent servir de base pour des reconstructions multi-échelles de scènes urbaines. Nous présentons d’abord un algorithme efficace pour le calcul de complexes simpliciaux à partir d’acquisitions LiDAR de scènes urbaines. Comme les complexes simpliciaux reconstruits peuvent être très lourds, ils peuvent être difficiles à traiter sur un ordinateur standard. Pour relever ce défi, nous étudions différentes approches pour les généraliser spatialement, en approximant de grandes zones géométriquement simples par des primitives simples. À cette fin, nous proposons un nouvel algorithme pour calculer des approximations planaires par morceaux de nuages de points 3D, basé sur une approche d’optimisation globale. Ensuite, nous proposons deux applications différentes des complexes simpliciaux. La première est une méthode de polygonalisation améliorant la création de modèles 3D légers mais géométriquement précis. La seconde est une méthode de classification faiblement supervisée utilisant des descripteurs 3D locaux et globaux
Thanks to their ever improving resolution and accessibility, Light Detection And Ranging (LiDAR) sensors are increasingly used for mapping cities. Indeed, these sensors are able to efficiently capture high-density scans, which can then be used to produce geometrically detailed reconstructions of complex scenes. However, such reconstruction requires organizing the scan with a fitting data structure, such as point clouds or meshes. Point clouds provide such a representation in a compact way, but their discrete nature prevents some applications such as visualization or simulation. Meshes allow for a continuous representation of surfaces, but are not well suited for representing complex objects, whose level of detail can exceed the resolution. To address these limitations, we propose to reconstruct a continuous geometry only where sufficient geometric information is available. This leads us to create a reconstruction mixing triangles, edges and points. We call such collection of objects a simplicial complex. In this thesis, we study the creation of geometrically detailed 3-dimensional (3D) models of urban scenes, based on simplicial complexes. We show that simplicial complexes are a suitable alternative to meshes. Indeed, they are fast to compute, and can be simplified while maintaining high geometric geometric fidelity with respect to the input scan. We argue that simplicial complexes convey valuable geometric information which can in turn be used for the semantization of 3D point clouds. We also think that they can serve as input for multi-scale reconstructions of urban scenes. We first present an efficient algorithm for computing simplicial complexes from LiDAR scans of urban scenes. Since the reconstructed simplicial complexes can be very large, they can be difficult to process on a standard computer. To handle this challenge, we investigate different approaches for their spatial generalization by approximating large and geometrically simple areas with simple primitives. To this end, we propose a new algorithm to compute piecewise-planar approximations of 3D point clouds, based on a global optimization approach. Next, we propose two different applications of simplicial complexes. The first one is a polygonalization method improving the creation of light yet geometrically accurate 3D models. The second one is a weakly-supervisedclassification method using 3D local and global descriptors

Un des nouveaux domaine de mathématiques pures appelé “géométrie tropicale” a vu un développement spectaculaire au cours de ces derniéres années. En géométrie énumérative, récemment Gregory Mikhalkin a donné une interprétation des invariants de Gromov-Witten en termes de géométrie tropicale en comptant des chemins entiers dans des polytopes entiers (Théorème de correspondance de Mikhalkin \cite{M2-04}). En utilisant des outils analogues, Andreas Gathmann et Hannah Markwig redécouvrent la formule de Caporaso-Harris pour les courbes complexes planes ainsi que les formules de Kontsevich pour les courbes rationnelles complexes et planes en termes de géométrie tropicale. Cette géométrie est liée à la géométrie algébrique classique par des objets géométriques appelés amibes et coamibes. La première terminologie, qui est la notion clef de la géométrie tropicale, est introduite pour la premiére fois en mathématiques par I. M. Gelfand, M. M. Kapranov et A. V. Zelevinsky en 1994. La seconde terminologie est introduite par M. Passare et A. Tsikh en 2000 dans plusieurs de leurs exposés un peu partout dans le monde. Ces formes de vie unicellulaires sont étudiées et bien connues en biologie. L'amibe plane est un objet géométrique qui fait allusion à une région ayant plusieurs trous (vocuolos) et des tentacules droites et pointues (pseudopodes). Ces tentacules atteignent l'infini et chacune d'elles se contracte exponentiellement vers un rayon (son squelette; voir la courte Note de Oleg Viro dans les Notes de l'AMS en 2002 pour une bref introduction sur les amibes). L'idée est de réduire à zéro l'épaisseur de ces amibes (bien sûr en essayant de garder le maximum d'informations géométriques , topologiques et autres propriétés de l'objet initial) et ainsi obtenir un objet tropical i. E. , purement combinatoire. Ce qui veut dire que les variétés tropicales apparaissent comme une certaine dégénérescence de ces objets. L'amibe d'une variété algébrique complexe dans l’espace complexe de dimension n est son image dans l’espace reel de dimension n par l'application logarithmique, c'est donc un objet qui vit dans l'espace réel, mais qui illustre de nombreuses caractéristiques de la variété complexe. On s'interesse dans cette these à la géométrie ainsi que la topologie de ces deux objets. On démontre plusieurs nouveaux réesultats concernant les coamibes, géométriques topologiques et combinatoires. On montre aussi leurs liens avec le polytope de Newton dans le cas des hypersurfaces, ainsi que leur similarités.

Dans plusieurs domaines de l'informatique graphique des structures combinatoires sont utilisées pour décrire des objets subdivisés en cellules (sommets, arêtes, faces, volumes, etc. ). Un problème commun à tous ces domaines est la caractérisation de propriétés structurelles (topologiques) des objets manipulés. L'homologie est un invariant topologique permettant de catactériser le nombre de "trous" d'un objet pour chaque dimension (i. E. Nombre de composantes connexes en dimension 0, nombre de trous en dimension 1, nombre de cavités en dimension 2, etc. ). Le cadre général de cette étude est le calcul de groupes d'homologie et des génerateurs de ces groupes pour des structures simpliciales, simploïdales et cellulaires. Le chapitre 2 introduit les notions de base de topologie. Dans le chapitre 3, nous décrivons et discutons de différentes méthodes de calcul (matricielles et incrémentales). Le chapitre 4 est consacré aux ensembles simploïdaux et au calcul de leurs groupes d'homologie
In many domains of computer graphics, combinatorial structures are used to describe objects subdivided into cells (vertices, edges, faces, volumes. . . ). A common problem in each domain is to characterize structural (topological) properties of handled objects. Homology is a topological invariant which characterizes the number of "holes" of an object in each dimension (i. E. Number of connected components in dimension 0, number of holes in dimension 1, number of cavities in dimension 2. . . ). The general framework of this study is the computation of homology groups and generators of these groups for simplicial, simploidal and cellular structures. Chapter 2 introduces basic notions of topology. In chapter 3, we describe different methods for computing homology groups (matricial and incremental). Chapter 4 is devoted to simploidal sets and to the computation of their homology groups

Représentations symboliques musicales et calcul spatial. La notion d'espace symbolique est fréquemment utilisée en théorie, analyse et composition musicale. La représentation de séquences dans des espaces de hauteurs, comme le Tonnetz, permet de capturer des propriétés mélodiques et harmoniques qui échappent aux systèmes de représentation traditionnels. Nous généralisons cette approche en reformulant d'un point de vue spatial différents problèmes musicaux (reconnaissance de style, transformations mélodiques et harmoniques, classification des séries tous-intervalles, etc.). Les espaces sont formalisés à l'aide de collections topologiques, une notion correspondant à la décoration d'un complexe cellulaire en topologie algébrique. Un complexe cellulaire per- met la représentation discrète d'un espace à travers un ensemble de cellules topologiques liées les unes aux autres par des relations de voisinage spécifiques. Nous représentons des objets musicaux élémentaires (par exemple des hauteurs ou des accords) par des cellules et construisons un complexe en les organisant suivant une relation de voisinage définie par une propriété musicale. Une séquence musicale est représentée dans un complexe par une trajectoire. L'aspect de la trajectoire révèle des informations sur le style de la pièce et les stratégies de composition employées. L'application d'opérations géométriques sur les trajectoires entraîne des transformations sur la pièce musicale initiale. Les espaces et les trajectoires sont construits à l'aide du langage MGS, un langage de programmation expérimental dédié au calcul spatial, qui vise à introduire la notion d'espace dans le calcul. Un outil, HexaChord, a été développé afin de faciliter l'utilisation de ces notions pour un ensemble prédéfinis d'espaces musicaux
Musical symbolic representations and spatial computing. The notion of symbolic space is frequently used in music theory, analysis and composition. Representing sequences in pitch (or chord) spaces, like the Tonnetz, enables to catch some harmonic and melodic properties that elude traditional representation systems. We generalize this approach by rephrasing in spatial terms different musical purposes (style recognition, melodic and harmonic transformations, all-interval series classification, etc.). Spaces are formalized as topological collections, a notion corresponding with the label- ling of a cellular complex in algebraic topology. A cellular complex enables the discrete representation of a space through a set of topological cells linked by specific neighborhood relationships. We represent simple musical objects (for example pitches or chords) by cells and build a complex by organizing them following a particular neighborhood relationship defined by a musical property. A musical sequence is represented in a complex by a trajectory. The look of the trajectory reveals some informations concerning the style of the piece, and musical strategies used by the composer. Spaces and trajectories are computed with MGS, an experimental programming language dedicated to spatial computing, that aims at introducing the notion of space in computation. A tool, HexaChord, has been developped in order to facilitate the use of these notions for a predefined set of musical spaces