Choice and chance, two chapters of arithmetic, with an appendix containing the algebraical treatment of permutations and combinations newly set forth.

Mode of access: Internet.

The combinatorics of Hilbert-Poincaré series of matroids

In this thesis we explore the combinatorial properties of several polynomials arising in matroid theory. Our main motivation comes from the problem of computing them in an efficient way and from a collection of conjectures, mainly the real-rootedness and the monotonicity of their coefficients with respect to weak maps. Most of these polynomials can be interpreted as Hilbert--Poincaré series of graded vector spaces associated to a matroid and thus some combinatorial properties can be inferred via combinatorial algebraic geometry (non-negativity, palindromicity, unimodality); one of our goals is also to provide purely combinatorial interpretations of these properties, for example by redefining these polynomials as poset invariants (via the incidence algebra of the lattice of flats); moreover, by exploiting the bases polytopes and the valuativity of these invariants with respect to matroid decompositions, we are able to produce efficient closed formulas for every paving matroid, a class that is conjectured to be predominant among all matroids. One last goal is to extend part of our results to a higher categorical level, by proving analogous results on the original graded vector spaces via abelian categorification or on equivariant versions of these polynomials.

A note on permutation regularity

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the Szemeredi Regularity Lemma in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partition given by Cooper (2006) [10], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence. (C) 2011 Elsevier B.V. All rights reserved.

Generating trees for permutations avoiding generalized patterns

We construct generating trees with with one, two, and three labels for some classes of permutations avoiding generalized patterns of length 3 and 4. These trees are built by adding at each level an entry to the right end of the permutation, which allows us to incorporate the adjacency condition about some entries in an occurrence of a generalized pattern. We use these trees to find functional equations for the generating functions enumerating these classes of permutations with respect to different parameters. In several cases we solve them using the kernel method and some ideas of Bousquet-Mélou [2]. We obtain refinements of known enumerative results and find new ones.

On square permutations

Severini and Mansour introduced in [4]square polygons, as graphical representations of square permutations, that is, permutations such that all entries are records (left or right, minimum or maximum), and they obtained a nice formula for their number. In this paper we give a recursive construction for this class of permutations, that allows to simplify the derivation of their formula and to enumerate the subclass of square permutations with a simple record polygon. We also show that the generating function of these permutations with respect to the number of records of each type is algebraic, answering a question of Wilf in a particular case.

Crosstalk between oestrogen receptors and thyroid hormone receptor isoforms results in differential regulation of the preproenkephalin gene

Nuclear receptors are ligand-activated transcription factors, which have the potential to integrate internal metabolic events in an organism, with consequences for control of behaviour. Previous studies from this laboratory have shown that thyroid hormone receptor (TR) isoforms can inhibit oestrogen receptor (ER)alpha-mediated induction of preproenkephalin (PPE) gene expression in the hypothalamus. Also, thyroid hormone administration inhibits lordosis, a behaviour facilitated by PPE expression. We have examined the effect of multiple ligand-binding TR isoforms on the ER-mediated induction of the PPE gene in transient transfection assays in CV-1 cells. On a natural PPE gene promoter fragment containing two putative oestrogen response elements (EREs), both ER alpha and beta isoforms mediate a four to five-fold induction by oestrogen. Cotransfection of TR alpha 1 along with ER alpha inhibited the ER alpha transactivation of PPE by approximately 50%. However, cotransfection with either TR beta 1 or TR beta 2 expression plasmids produced no effect on the ER alpha or ER beta mediated induction of PPE. Therefore, under these experimental conditions, interactions with a single ER isoform are specific to an individual TR isoform. Transfection with a TR alpha 1 DNA-binding mutant could also inhibit ER alpha transactivation, suggesting that competition for binding on the ERE may not be the exclusive mechanism for inhibition. Data with the coactivator, SRC-1, suggested that coactivator squelching may participate in the inhibition. In dramatic contrast, when ER beta is cotransfected, TR alpha 1 stimulated ER beta-mediated transactivation of PPE by approximately eight-fold over control levels. This is the first study revealing specific interactions among nuclear receptor isoforms on a neuroendocrine promoter. These data also suggest that the combinatorics of ER and TR isoforms allow multiple forms of flexible gene regulations in the service of neuroendocrine integration.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Region-Based Feature Interpretation for Recognizing 3D Models in 2D Images

In model-based vision, there are a huge number of possible ways to match model features to image features. In addition to model shape constraints, there are important match-independent constraints that can efficiently reduce the search without the combinatorics of matching. I demonstrate two specific modules in the context of a complete recognition system, Reggie. The first is a region-based grouping mechanism to find groups of image features that are likely to come from a single object. The second is an interpretive matching scheme to make explicit hypotheses about occlusion and instabilities in the image features.

Triangulation by Continuous Embedding

When triangulating a belief network we aim to obtain a junction tree of minimum state space. Searching for the optimal triangulation can be cast as a search over all the permutations of the network's vaeriables. Our approach is to embed the discrete set of permutations in a convex continuous domain D. By suitably extending the cost function over D and solving the continous nonlinear optimization task we hope to obtain a good triangulation with respect to the aformentioned cost. In this paper we introduce an upper bound to the total junction tree weight as the cost function. The appropriatedness of this choice is discussed and explored by simulations. Then we present two ways of embedding the new objective function into continuous domains and show that they perform well compared to the best known heuristic.

Rigidity for piecewise smooth homeomorphisms on the circle

We find conditions for two piecewise 'C POT.2+V' homeomorphisms f and g of the circle to be 'C POT.1' conjugate. Besides the restrictions on the combinatorics of the maps (we assume that the maps have bounded combinatorics), and necessary conditions on the one-side derivatives of points where f and g are not differentiable, we also assume zero mean-nonlinearity for f and g.

Die Rolle von Hopfkategorien und Operaden in störungstheoretischen Quantenfeldtheorien

Die Vorhersagen störungstheoretischer Quantenfeldtheorienzeigen eine gute Übereinstimmung mit experimentellgemessenen Werten. Bei diesen störungstheoretischenBerechnungen treten allerdings Ultraviolettdivergenzen auf,die keine physikalische Interpretation der Ergebnisseermöglichen. Durch Renormierung dieser Theorien erhält manjedoch berechnbare Ergebnisse mit hoher experimentellerVorhersagekraft. Der Renormierungsvorgang kann durch eineHopfalgebra, die sogenannte 'Hopfalgebra der Wurzelbäume',beschrieben werden.Die vorliegende Arbeit leistet einen Beitrag für weitereUntersuchungen dieser Hopfalgebrenstruktur und Bestimmungneuer mathematischer Methoden zur Beschreibung desRenormierungsvorgangs. Dazu wird die algebraische Strukturvon Renormierung aus der Sicht der Kategorientheorie und derTheorie von Operaden untersucht.Aus Sicht der Kategorientheorie lassen sich die den Renormierungsprozess beschreibenden mathematischen Größen ineiner Kategorie zusammenfassen. Eine additive Strukturermöglicht dabei die Berücksichtigung beliebigerRenormierungsschemata. Auf dieser Kategorie kann einassoziativitätsverletzendes Produkt definiert werden, wobeidie Verletzung durch einen sogenannten 'Assoziator'kontrolliert werden kann. Die Struktur wird auf die einerHopfkategorie erweitert, so daß eine kategorientheoretischeUntersuchung des Renormierungsprozesses ermöglicht wird.Diese Hopfkategorie wird aus Sicht von Renormierunginterpretiert, wobei Beispielrechnungen die definierteStruktur verdeutlichen.Aus algebraischer Sicht kann aufgrund der graphischenDarstellung des Operadenproduktes eine Bijektivität zwischenWurzelbäumen und Operaden gezeigt werden. Auf diesenOperaden kann wiederum eine Hopfalgebrenstruktur definiertwerden. Beispiele verdeutlichen diese Bijektivität.

Permutation classes, sorting algorithms, and lattice paths

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Inovação e indústria da moda: um modelo de inovação em estilos e tendências.

Este trabalho tem como intuito propor um modelo de inovação para a indústria da moda feminina. O modelo visa compreender o comportamento de estilos e tendências determinados e difundidos pelas empresas. A construção deste modelo é justificada pela contribuição que um estudo sobre inovação pode proporcionar à indústria da moda, a qual enfrenta baixos padrões de competitividade no mercado externo e interno. Além disso, embora existam muitos artigos sobre o assunto, poucos foram os modelos de inovação para a indústria da moda encontrados por esta pesquisa. Uma avaliação destes modelos indicou que existe espaço para a proposta de um modelo que aborde o comportamento de estilos e tendências ao longo do tempo. A estrutura de composição do modelo é sustentada por três pilares conceituais: teoria econômica neoschumpeteriana, modelos de inovação e modelos de inovação para a indústria da moda. A característica central do modelo é avaliar se existem estilos que permanecem em moda de maneira contínua ou descontínua. Como existe similaridade conceitual entre os estilos, no que se refere à identidade de gênero (androginia e feminilidade), foi efetuada uma aglutinação de alguns estilos dentro desta denominação. Nem todos os estilos se encaixaram nesta classificação. Então, estes estilos foram denominados como neutros. Como a pesquisa tem abordagem fenomenológica, qualitativa e longitudinal, foi adotada a metodologia hipotética dedutiva para a construção do modelo. Para verificação da validade das hipóteses foi usada uma análise exploratória dos dados por meio de estatística descritiva e decomposição da estrutura de variabilidade através de uma análise de componentes principais (PCA). Ambas as análises forneceram evidências a respeito das hipóteses em questão, as quais também foram testadas através de um teste binomial e de uma análise de variância multivariada por meio de permutações. Os resultados comprovaram que existem estilos que permanecem em moda de maneira contínua e que existem períodos de polarização das aglutinações de estilo.