To see the other types of publications on this topic, follow the link: Partitions.
Dissertations / Theses on the topic 'Partitions'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Partitions.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Dogaru, Ioana. "Canonical partitions." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq24655.pdf.
Full text
2
French, Jennifer. "Vector Partitions." Digital Commons @ East Tennessee State University, 2018. https://dc.etsu.edu/etd/3392.
Full textAbstract:
Integer partitions have been studied by many mathematicians over hundreds of years. Many identities exist between integer partitions, such as Euler’s discovery that every number has the same amount of partitions into distinct parts as into odd parts. These identities can be proven using methods such as conjugation or generating functions. Over the years, mathematicians have worked to expand partition identities to vectors. In 1963, M. S. Cheema proved that every vector has the same number of partitions into distinct vectors as into vectors with at least one component odd. This parallels Euler’s result for integer partitions. The primary purpose of this paper is to use generating functions to prove other vector partition identities that parallel results of integer partitions.
3
Johnson, William E. "TONE ROW PARTITIONS IN SCHOENBERG'S MOSES UND ARON The Volk Partition and the Zwischenspiel Partition." Digital Commons @ Butler University, 2015. http://digitalcommons.butler.edu/grtheses/264.
Full textAbstract:
Arnold Schoenberg's development of twelve-tone serial ism in the early 20th Century had profound and far-reaching impact on the musical world. As Schoenberg himself grew and matured as a composer, so did the compositional technique of, and indeed his proficiency with, serialism. The opera Moses und Aron was composed in Schoenberg's third compositional period that lasted from 1923 through Schoenberg's death in 1951 and was characterized almost exclusively by this new technique of twelvetone serialism. Moses und Aron's first two Acts (as well as the libretto for the third) were written from 1930 to 1932 and based entirely on a single tone row. Though the opera itself was composed in the early 1930s, it had its beginnings as a religious play, similar to Schoenberg's earlier work, Oer Biblische Weg. Schoenberg left the opera as it was in 1932 and failed to return to score the libretto in Act III. Despite remaining unfinished, Moses und Aron is still widely regarded as one of Schoenberg's finest works and displays a composer working at the height of his skill.
This project brings to light the brilliance of the tone row Schoenberg chose as his foundation for Moses und Aron through examining the various tone row transformations used throughout the opera as well as their specific setting and orchestration within the context of each scene. More than simply a musical background for the dramatic events of the Exodus narrative, the tone row becomes a character in-and-of itself, transforming and shifting to mirror dramatic events and becoming a driving force throughout the opera. In addition to informing dramatic content and context, the way in which Schoenberg scores the tone row also helps to illuminate the large scale musical form of each scene and is even essential to the dramatic tension and characterization within the narrative.
In addition, this project endeavors to show that Moses und Aron displays Schoenberg's mastery of the compositional technique of twelve-tone serialism by examining in detail the significance of the functional orchestration as well as the divisions, or partitions, of Schoenberg's twelve-tone row. Inseparably connected with a discussion of the functional orchestration and partitioning of Schoenberg's tone row is a discussion of the different kinds of counterpoint that often occur as a result of such partitioning within the choral and instrumental orchestration of Moses und Aron. These concepts of functional orchestration, partitioning, and multiple forms of counterpoint are defined and unpacked in the upcoming chapters. As counterpoint functions as such an important aspect of the partitioning of the tone row, a brief discussion of counterpoint in serialism, specifically in Moses und Aron, accompanies the discussion of functional orchestration and the row partitioning. This understanding of the function of counterpoint in twelve-tone serial atonality is essential to this study.
Much has been written, specifically by Michael Cherlin, about the formal and dramatic organization of Moses und Aron and how Schoenberg's permutations of his tone row both influence and are influenced by the formal and dramatic context. Cherlin has also given significant attention to defining links between tone row partitions and dramatic events or characters within Moses und Aron. An important part of my research, therefore, includes examining the analytical findings of Cherlin as well as those from other scholarly sources. This project also challenges or supports these findings based on my own analysis and discusses what I believe to be a new facet of the organization of Moses und Aron not previously revealed in other studies. In Chapter 5 of this project, I bring to light two specific partitions of the row that occur within the choral counterpoint of the opera and have not been mentioned in any study of Moses und Aron that I have discovered in my research.
4
Yip, Martha. "Genus one partitions." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2933.
Full textAbstract:
We obtain a tight upper bound for the genus of a partition, and calculate the number of partitions of maximal genus. The generating series for genus zero and genus one rooted hypermonopoles is obtained in closed form by specializing the genus series for hypermaps. We discuss the connection between partitions and rooted hypermonopoles, and suggest how a generating series for genus one partitions may be obtained via the generating series for genus one rooted hypermonopoles. An involution on the poset of genus one partitions is constructed from the associated hypermonopole diagrams, showing that the poset is rank-symmetric. Also, a symmetric chain decomposition is constructed for the poset of genus one partitions, which consequently shows that it is strongly Sperner.
5
Jagger, Christopher Neil. "Partitions of graphs." Thesis, University of Cambridge, 1995. https://www.repository.cam.ac.uk/handle/1810/251583.
Full text
6
Waugh, Karl Michael Vincent. "Partitions of codes." Thesis, University of Sussex, 2013. http://sro.sussex.ac.uk/id/eprint/45301/.
Full textAbstract:
In this thesis we look at coding theory wherein we introduce the concept of perspective, a generalisation on the minimum distance of a code, which naturally leads to a partition of the code. Subsequently we introduce focused splittings, which shall be shown to be a generalisation of perfect codes. We investigate the existence of such objects, and address questions such as the complexity of finding a focused splittings, which we show to be NPComplete. We analyse the symmetries of focused splittings. We use focused splittings to address the problem of error correction and we construct an encoding method based on them. Finally we test this construction for various classes of focused splittings.
7
Bustamante, Franco Sebastián Felipe. "Hypergraph cycle partitions." Tesis, Universidad de Chile, 2018. http://repositorio.uchile.cl/handle/2250/168156.
Full textAbstract:
Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Modelación MatemáticaThe main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ with $k \geq 2$, the vertices of every $r(k-1)$-edge-coloured countably infinite complete $k$-uniform hypergraph can be core-partitioned into at most $r$ monochromatic Berge-cycles of different colours. We further describe a construction showing that this result is best possible. The second part deals with $\ell$-cycles. We show that for all $\ell, k, n \in \N$ with $\ell \leq k/2$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete graph on $n$ vertices has at most two disjoint monochromatic $\ell$-cycles in different colours that together cover all but a constant number of vertices, where the constant depends on $k$ and $\ell$. Furthermore, we can cover all vertices with at most $4$ ($3$ if $\ell \leq k/3$) disjoint monochromatic $\ell$-cycles. The third part deals with tight-cycles in $2$-edge-colourings of complete $3$-uniform hypergraphs. We show that for every $\eta > 0$ there exists an integer $n_0$ such that every $2$-edge-colouring of the $3$-uniform complete hypergraph on $n \geq n_0$ vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most $\eta n$ vertices. Finally, the fourth part deals with tight-cycles in a more general setting. We prove that for every $k,r \in \N$, the vertices of every $r$-edge-coloured complete $k$-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles, confirming a conjecture of Gy\'arf\'as. We further prove that for every $r,p \in \N$, the vertices of every $r$-edge-coloured complete graph can be partitioned into a bounded number of $p$-th powers of cycles, settling a problem of Elekes, D. Soukup, L. Soukup and Szentmikl\'ossy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs with bounded independence number.
CONICYT/Doctorado Nacional/2014-21141116, CMM-Conicyt PIA AFB170001
8
Lang, Richard Johannes. "Monochromatic cycle partitions." Tesis, Universidad de Chile, 2017. http://repositorio.uchile.cl/handle/2250/147415.
Full textAbstract:
Doctor en Ciencias de la Ingeniería, Mención Modelación MatemáticaThe first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ vertices of the graph. In the same situation, 18 disjoint monochromatic cycles together cover all vertices. Next we show that given any $2$-local edge-colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most $3$ disjoint monochromatic paths. And, we can cover all vertices of any complete or balanced complete bipartite $r$-locally edge-coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path: Every $2$-local edge-colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices. Finally, we prove that any edge-colouring in red and blue of a graph on $n$ vertices and of minimum degree $2n/3 + o(n)$ admits a partition into three monochromatic cycles. This confirms a conjecture of Pokrovskiy approximately. The second part of this thesis contains two independent results about (proper) edge-colouring and parameter estimation respectively. With regards to edge-colouring, we conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. Concerning parameter estimation we study, for any fixed monotone graph property $\mathcal{P}=\text{Forb}(\mathcal{\mathcal{F}})$, the sample complexity of estimating a bounded graph parameter $z_{\mathcal{\mathcal{F}}}$ that, for an input graph $G$, counts the number of {spanning} subgraphs of $G$ that satisfy $\mathcal{P}$. Using a new notion of vertex partitions, we improve upon previous upper bounds on the sample complexity of estimating $z_{\mathcal{\mathcal{F}}}$.
9
Rybnikov, Konstantin. "Polyhedral partitions and stresses." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/NQ45268.pdf.
Full text
10
Dent, Suzie C. "Incidence structures of partitions." Thesis, University of East Anglia, 1997. https://ueaeprints.uea.ac.uk/38276/.
Full text
11
Patel, Viresh. "Partitions of combinatorial structures." Thesis, London School of Economics and Political Science (University of London), 2009. http://etheses.lse.ac.uk/3006/.
Full textAbstract:
In this thesis we explore extremal, structural, and algorithmic problems involving the partitioning of combinatorial structures. We begin by considering problems from the theory of graph cuts. It is well known that every graph has a cut containing at least half its edges. We conjecture that (except for one example), given any two graphs on the same vertex set, we can partition the vertices so that at least half the edges of each graph go across the partition. We give a simple algorithm that comes close to proving this conjecture. We also prove, using probabilistic methods, that the conjecture holds for certain classes of graphs. We consider an analogue of the graph cut problem for posets and determine which graph cut results carry over to posets. We consider both extremal and algorithmic questions, and in particular, we show that the analogous maxcut problem for posets is polynomial-time solvable in contrast to the maxcut problem for graphs, which is NP-complete. Another partitioning problem we consider is that of obtaining a regular partition (in the sense of the Szemeredi Regularity Lemma) for posets, where the partition respects the order of the poset. We prove the existence of such order-preserving, regular partitions for both the comparability graph and the covering graph of a poset, and go on to derive further properties of such partitions. We give a new proof of an old result of Frankl and Furedi, which characterises all 3-uniform hypergraphs for which every set of 4 vertices spans exactly 0 or 2 edges. We use our new proof to derive a corresponding stability result. We also look at questions concerning an analogue of the graph linear extension problem for posets.
12
Murakami, Yuko. "Modal logic of partitions." [Bloomington, Ind.] : Indiana University, 2005. http://wwwlib.umi.com/dissertations/fullcit/3162977.
Full textAbstract:
Thesis (Ph.D.)--Indiana University, Dept. of Philosophy, 2005.Title from PDF t.p. (viewed Dec. 2, 2008). Source: Dissertation Abstracts International, Volume: 66-02, Section: A, page: 0620. Chairs: Lawrence Moss; Michael Dunn.
13
Lachniet, Jason. "Alliance Partitions in Graphs." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2080.
Full textAbstract:
For a graph G=(V,E), a nonempty subset S contained in V is called a defensive alliance if for each v in S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. If there are strictly more vertices from the closed neighborhood of v in S as in V-S, then S is a strong defensive alliance. A (strong) defensive alliance is called global if it is also a dominating set of G. The alliance partition number (respectively, strong alliance partition number) is the maximum cardinality of a partition of V into defensive alliances (respectively, strong defensive alliances). The global (strong) alliance partition number is defined similarly. For each parameter we give both general bounds and exact values. Our major results include exact values for the alliance partition number of grid graphs and for the global alliance partition number of caterpillars.
14
Phometsi, Mothusi. "Economic evaluation of flexible partitions." Thesis, Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/34774.
Full textAbstract:
Corporate Real Estate (CRE) investors are often confronted with a need for flexibility in buildings. They often embark on costly renovations to accommodate changing use requirements. When new needs arise, landlords and tenants often risk loss due to inability to easily switch to configurations that can meet those needs. The main cause for this problem is lack of a planning model that can allow buildings to easily evolve over time allowing decision-makers to hedge investment positions against risk due to uncertainty.
The emergence of Real Options (RO) theory in the 1970's has led to debates in search of a better planning model for real projects. The success of RO application in building construction (BC) hinges on the development of models that can be used to assess economic performance of flexible design options (FDO) in building systems. For building interior spaces, there is currently no model that can value flexibility of partition systems. The purpose of this study is to present a model that can be used to value flexibility in mutually exclusive partition systems over a project's life span. The proposed model uses decision tree representation, stochastic forecasting and random sampling of decision-path scenarios to generate cumulative risk profiles of partition systems' life cycle costs with expected median value, standard deviation and variance to inform decision making under uncertainty.
The research processes include: assumptions, decision-making structure for identification of uncertain variable, model representation, spreadsheet programming, Monte Carlo simulation, and validation. The model will enable application of RO "in" BC projects.
15
Zoghbi, Antoine C. "Algorithms for generating integer partitions." Thesis, University of Ottawa (Canada), 1993. http://hdl.handle.net/10393/6506.
Full textAbstract:
In this thesis we consider the problem of generating integer partitions. We provide an overview of all known algorithms for the sequential generation of partitions of an integer. The performance is measured and compared separately for the standard and multiplicity representation of integer partitions. We present two new algorithms for generating integer partitions in the standard representation which generate partitions in lexicographic and antilexicographic order respectively. We prove that both algorithms generate partitions with constant average delay (exclusive of the output; output is generated and not printed). Historically, all existing algorithms for generating integer partitions in the multiplicity representation showed better performance than all the existing algorithms for generating integer partitions in the standard representation. An empirical test shows that both new algorithms are a few times faster than any previously known algorithms for generating unrestricted integer partitions in the standard representation. Moreover, they are faster than any known algorithm for generating integer partitions in the multiplicity representation (exclusive of the output). We describe several modifications to existing algorithms, and a transformation of one algorithm from the standard to the multiplicity representation. Finally, we provide a brief overview of sequential and parallel algorithms that generate partitions at random, and an analysis of a parallel algorithm for generating all partitions.
16
Asplund, Mikael. "Restoring Consistency after Network Partitions." Licentiate thesis, Linköping : Linköpings universitet, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-9913.
Full text
17
Johnson, J. R. "Baranyai partitions and Kneser graphs." Thesis, University of Cambridge, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.605621.
Full textAbstract:
The Kneser graph K(n,r) has vortex set consisting of all the r-sets of a fixed n-set with two vertices being adjacent if the corresponding sets are disjoint. This thesis is mainly concerned with structural properties of this intriguing family of graphs and related combinatorial objects. As well as the general Kneser graph we study the Odd graphs, that is the subfamily of the Kneser graphs formed by taking n = 2r + 1, and subgraphs of the discrete cube related to K(n,r) via graph homomorphisms. In particular, we will be concerned with the existence of Hamilton cycles, and related issues such as cycle lengths and 2-factors in these graphs. Among the results which we prove in this area are the existence of cycles through a proportion arbitrarily close to 1 of the vertices of the Middle Two Layers graph and the Kneser graph, the existence of a 2-factorisation of the Odd graph, a second proof (following Chen) of the existence of a Hamilton cycle in K(n,r) when n ³ 3r, and an inductive construction which extends the range of values for which the Kneser graph is known to be Hamiltonian. We also study partitions of the vertex set of K(3k,3), where k is an integer, into complete graphs of order k. The existence of such a partitioning is a consequence of Baranyai’s Partition theorem. We address the question of whether such a partitioning can be made to satisfy a certain natural ‘separatedness’ condition, as conjectured by Fon-der-Flaass. Our main result here is that Fon-der-Flaass’ conjecture fails for n = 12.
18
Chen, Xujin, and 陳旭瑾. "Graph partitions and integer flows." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2004. http://hub.hku.hk/bib/B30286256.
Full text
19
Capitaine, Thierry. "Reconnaissance optique de partitions musicales." Compiègne, 1995. http://www.theses.fr/1995COMPD852.
Full textAbstract:
La reconnaissance optique de partitions musicales reste un problème complexe à cause des lignes de portées qui relient entre-elles les différents symboles. C'est pour cette raison que les démarches classiques tentent de les supprimer par l'utilisation d'algorithmes complexes ne scindant pas les symboles. Notre approche s'appuie sur une exploitation directe des positions de ces lignes et sur la création d'interlignes virtuelles en tenant compte de la signification musicale qu'elles engendrent. Afin de limiter l'influence du biais, leur détection n'apparaît qu'au niveau des mesures. Il en est de même des phases de segmentation et de reconnaissance qui peuvent alors s'appuyer sur le contexte musical local à chaque mesure. Ces lignes et interlignes définissent les limites de 2x13 cumuls perpendiculaires (clef de Fa et clef de Sol) pour détecter la présence d'informations musicales (patterns). Ces derniers sont codés par trois caractères en fonction de leur forme, de leur hauteur et largeur. L'analyse de la position de ces derniers, associée avec les règles de positionnement des symboles musicaux, permet d'obtenir une représentation sous forme de chaîne de caractères de deux classes de symboles musicaux (analyse horizontale pour les liaisons et verticale pour les autres). Ces chaînes alimentent un analyseur syntaxique qui réalise la reconnaissance finale en tenant compte de leur signification musicale. Le contrôle du nombre de temps joués associé à la tonalité de chaque mesure et de l'historique des altérations rencontrées permettent de valider la reconnaissance. Les résultats obtenus pour diverses partitions de différentes tailles et orientations valident notre approche (90% de reconnaissance pour les symboles principaux).
20
Barakat, Maher. "Partitions arborescentes et compression fractale." Toulouse, INPT, 2000. http://www.theses.fr/2000INPT001H.
Full textAbstract:
La compression fractale fait partie des méthodes de compression d'images irréversibles. Sa relative jeunesse en fait l'un des champs privilégiés d'investigation en compression d'images numériques. Divers travaux ont montré que cette méthode possède un potentiel lui permettant de figurer parmi les méthodes de compression efficaces. La compression fractale "quantifie" les blocs d'une partition de l'image en les représentant par des transformations simples. L'amélioration du compromis débit-distorsion de cette méthode peut se faire via une partition judicieuse du support de l'image. Bien que la plupart des études sur la compression fractale optent pour des partitions en arbre quaternaire, d'autres types de partitions adaptatives ont été tentées. Le présent travail est une contribution à l'étude du choix de la partition dans un codeur fractal. Les partitions étudiées sont à structure arborescente. Nous nous intéressons plus particulièrement aux partitions en arbre binaire. Nous traitons le problème de la construction optimale de l'arbre. Nous appliquons un algorithme optimal à la construction de l'arbre dans un codeur fractal. Nous étudions, entre autres, l'influence du nombre des directions de division sur le compromis débit-distorsion. Enfin, nous comparons la partition en arbre binaire aux partitions adaptatives étudiées précédemment.
21
Cullion, Paul D. "3-Regularizing 3-semiFayers Partitions." University of Akron / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=akron1335230915.
Full text
22
Edmonds, Rex W. "Friendly and Unfriendly k-Partitions." Youngstown State University / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=ysu1420640472.
Full text
23
Bensmail, Julien. "Partitions et décompositions de graphes." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0062/document.
Full textAbstract:
Cette thèse est dédiée à l’étude de deux familles de problèmes de partition de graphe. Nous considérons tout d’abord le problème de sommet-partitionner un graphe en sous-graphesconnexes. Plus précisément, étant donnés p entiers positifs n1; n2; :::; np dont la somme vautl’ordre d’un graphe G, peut-on partitionner V (G) en p parts V1; V2; :::; Vp de sorte que chaque Vi induise un sous-graphe connexe d’ordre ni ? Nous nous intéressons ensuite à des questions plus fortes. Que peut-on dire si l’on souhaite que G soit partitionnable de cette manière quels que soient p et n1; n2; :::; np ? Si l’on souhaite que des sommets particuliers de G appartiennent à des sous-graphes particuliers de la partition ? Et si l’on souhaite que les sous-graphes induits soient plus que connexes ? Nous considérons toutes ces questions à la fois du point de vue structurel (sous quelles conditions structurelles une partition particulière existe-t-elle nécessairement ?) et algorithmique (est-il difficile de trouver une partition particulière ?).Nous nous intéressons ensuite à la 1-2-3 Conjecture, qui demande si tout graphe G admet une 3-pondération voisin-somme-distinguante de ses arêtes, i.e. une 3-pondération par laquelle chaque sommet de G peut être distingué de ses voisins en comparant uniquement leur somme de poids incidents. Afin d’étudier la 1-2-3 Conjecture, nous introduisons notamment la notionde coloration localement irrégulière d’arêtes, qui est une coloration d’arêtes dont chaque classe de couleur induit un sous-graphe dans lequel les sommets adjacents sont de degrés différents.L’intérêt principal de cette coloration est que, dans certaines situations, une pondération d’arêtes voisin-somme-distinguante peut être déduite d’une coloration d’arêtes localement irrégulière. Nospréoccupations dans ce contexte sont principalement algorithmiques (est-il facile de trouver une pondération d’arêtes voisin-somme-distinguante ou une coloration d’arêtes localement irrégulière utilisant le plus petit nombre possible de poids ou couleurs ?) et structurelles (quel est le plus petit nombre de couleurs d’une coloration d’arêtes localement irrégulière ?). Nous considérons également ces questions dans le contexte des graphes orientésThis thesis is dedicated to the study of two families of graph partition problems.First, we consider the problem of vertex-partitioning a graph into connected subgraphs.Namely, given p positive integers n1; n2; :::; np summing up to the order of some graph G, canwe partition V (G) into p parts V1; V2; :::; Vp so that each Vi induces a connected subgraph withorder ni? We then consider stronger questions. Namely, what if we want G to be partitionablewhatever are p and n1; n2; :::; np? What if we also want specific vertices of G to belong to somespecific subgraphs induced by the vertex-partition? What if we want the subgraphs induced bythe vertex-partition to be more than connected? We consider all these questions regarding boththe structural (are there structural properties ensuring that a specific vertex-partition necessarilyexists?) and algorithmic (is it hard to deduce a specific vertex-partition?) points of view.Then, we focus on the so-called 1-2-3 Conjecture, which asks whether every graph G admitsa neighbour-sum-distinguishing 3-edge-weighting, i.e. a 3-edge-weighting by which all adjacentvertices of G get distinguished by their sums of incident weights. As a tool to deal with the1-2-3 Conjecture, we notably introduce the notion of locally irregular edge-colouring, which isan edge-colouring in which every colour class induces a subgraph whose adjacent vertices havedistinct degrees. The main point is that, in particular situations, a neighbour-sum-distinguishingedge-weighting of G can be deduced from a locally irregular edge-colouring of it. Our concernsin this context are mostly algorithmic (can we easily find a neighbour-sum-distinguishing edgeweightingor locally irregular edge-colouring using the least number of weights or colours?) andstructural (what is the least number of colours in a locally irregular edge-colouring?). We alsoconsider similar matters in the context of oriented graphs
24
Fergusson, Kevin John. "Partitions into large unequal parts /." Title page, contents and abstract only, 1996. http://web4.library.adelaide.edu.au/theses/09PH/09phf354.pdf.
Full text
25
Quéré, Romain. "Quelques propositions pour la comparaison de partitions non strictes." Phd thesis, Université de La Rochelle, 2012. http://tel.archives-ouvertes.fr/tel-00950514.
Full textAbstract:
Cette thèse est consacrée au problème de la comparaison de deux partitions non strictes (floues/probabilistes, possibilistes) d'un même ensemble d'individus en plusieurs clusters. Sa résolution repose sur la définition formelle de mesures de concordance reprenant les principes des mesures historiques développées pour la comparaison de partitions strictes et trouve son application dans des domaines variés tels que la biologie, le traitement d'images, la classification automatique. Selon qu'elles s'attachent à observer les relations entre les individus décrites par chacune des partitions ou à quantifier les similitudes entre les clusters qui composent ces partitions, nous distinguons deux grandes familles de mesures pour lesquelles la notion même d'accord entre partitions diffère, et proposons d'en caractériser les représentants selon un même ensemble de propriétés formelles et informelles. De ce point de vue, les mesures sont aussi qualifiées selon la nature des partitions comparées. Une étude des multiples constructions sur lesquelles reposent les mesures de la littérature vient compléter notre taxonomie. Nous proposons trois nouvelles mesures de comparaison non strictes tirant profit de l'état de l'art. La première est une extension d'une approche stricte tandis que les deux autres reposent sur des approches dite natives, l'une orientée individus, l'autre orientée clusters, spécifiquement conçues pour la comparaison de partitions non strictes. Nos propositions sont comparées à celles de la littérature selon un plan d'expérience choisi pour couvrir les divers aspects de la problématique. Les résultats présentés montrent l'intérêt des propositions pour le thème de recherche qu'est la comparaison de partitions. Enfin, nous ouvrons de nouvelles perspectives en proposant les prémisses d'un cadre qui unifie les principales mesures non strictes orientées individus.
26
Halbeisen, Lorenz J. "Ramsey properties of reals and partitions /." [S.l.] : [s.n.], 1994. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=10828.
Full text
27
Ma, Jie. "Judicious partitions of graphs and hypergraphs." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41064.
Full textAbstract:
Classical partitioning problems, like the Max-Cut problem, ask for partitions that optimize one quantity, which are important to such fields as VLSI design, combinatorial optimization, and computer science. Judicious partitioning problems on graphs or hypergraphs ask for partitions that optimize several quantities simultaneously. In this dissertation, we work on judicious partitions of graphs and hypergraphs, and solve or asymptotically solve several open problems of Bollobas and Scott on judicious partitions, using the probabilistic method and extremal techniques.
28
Kenny, Robert. "Orbit complexity and computable Markov partitions." University of Western Australia. School of Mathematics and Statistics, 2008. http://theses.library.uwa.edu.au/adt-WU2008.0231.
Full textAbstract:
Markov partitions provide a 'good' mechanism of symbolic dynamics for uniformly hyperbolic systems, forming the classical foundation for the thermodynamic formalism in this setting, and remaining useful in the modern theory. Usually, however, one takes Bowen's 1970's general construction for granted, or restricts to cases with simpler geometry (as on surfaces) or more algebraic structure. This thesis examines several questions on the algorithmic content of (topological) Markov partitions, starting with the pointwise, entropy-like, topological conjugacy invariant known as orbit complexity. The relation between orbit complexity de nitions of Brudno and Galatolo is examined in general compact spaces, and used in Theorem 2.0.9 to bound the decrease in some of these quantities under semiconjugacy. A corollary, and a pointwise analogue of facts about metric entropy, is that any Markov partition produces symbolic dynamics matching the original orbit complexity at each point. A Lebesgue-typical value for orbit complexity near a hyperbolic attractor is also established (with some use of Brin-Katok local entropy), and is technically distinct from typicality statements discussed by Galatolo, Bonanno and their co-authors. Both our results are proved adapting classical arguments of Bowen for entropy. Chapters 3 and onwards consider the axiomatisation and computable construction of Markov partitions. We propose a framework of 'abstract local product structures'
29
Fevens, Thomas. "Partitions and coverings of point sets." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0004/NQ42995.pdf.
Full text
30
Broutin, Nicolas. "Random trees, graphs and recursive partitions." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00842019.
Full textAbstract:
Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:Arbres aléatoires uniformes. Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.
Graphes aléatoires. J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. Arbres couvrant minimaux. J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.
31
KIM, SUNGSOON. "Hauteurs sur le treillis des partitions." Paris 7, 1995. http://www.theses.fr/1995PA077215.
Full textAbstract:
Nous definissons une notion de hauteur sur le treillis des partitions. Pour cela nous comparons les partitions a certains elements speciaux (ceux qui n'ont qu'un successeur). Nous decrivons aussi certains intervalles speciaux et des sous-treillis distributifs lies a des questions de theories des representations et de geometrie enumerative
32
Stacklin, Thomas M. "Random partitions of integers into squares /." The Ohio State University, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=osu1488205318509902.
Full text
33
Williams, Jake Ryland. "Lexical mechanics: Partitions, mixtures, and context." ScholarWorks @ UVM, 2015. http://scholarworks.uvm.edu/graddis/346.
Full textAbstract:
Highly structured for efficient communication, natural languages are complex systems. Unlike in their computational cousins, functions and meanings in natural languages are relative, frequently prescribed to symbols through unexpected social processes. Despite grammar and definition, the presence of metaphor can leave unwitting language users "in the dark," so to speak. This is not problematic, but rather an important operational feature of languages, since the lifting of meaning onto higher-order structures allows individuals to compress descriptions of regularly-conveyed information. This compressed terminology, often only appropriate when taken locally (in context), is beneficial in an enormous world of novel experience. However, what is natural for a human to process can be tremendously difficult for a computer. When a sequence of words (a phrase) is to be taken as a unit, suppose the choice of words in the phrase is subordinate to the choice of the phrase, i.e., there exists an inter-word dependence owed to membership within a common phrase. This word selection process is not one of independent selection, and so is capable of generating word-frequency distributions that are not accessible via independent selection processes. We have shown in Ch. 2 through analysis of thousands of English texts that empirical word-frequency distributions possess these word-dependence anomalies, while phrase-frequency distributions do not. In doing so, this study has also led to the development of a novel, general, and mathematical framework for the generation of frequency data for phrases, opening up the field of mass-preserving mesoscopic lexical analyses. A common oversight in many studies of the generation and interpretation of language is the assumption that separate discourses are independent. However, even when separate texts are each produced by means of independent word selection, it is possible for their composite distribution of words to exhibit dependence. Succinctly, different texts may use a common word or phrase for different meanings, and so exhibit disproportionate usages when juxtaposed. To support this theory, we have shown in Ch. 3 that the act of combining distinct texts to form large 'corpora' results in word-dependence irregularities. This not only settles a 15-year discussion, challenging the current major theory, but also highlights an important practice necessary for successful computational analysis---the retention of meaningful separations in language. We must also consider how language speakers and listeners navigate such a combinatorially vast space for meaning. Dictionaries (or, the collective editorial communities behind them) are smart. They know all about the lexical objects they define, but we ask about the latent information they hold, or should hold, about related, undefined objects. Based solely on the text as data, in Ch. 4 we build on our result in Ch. 2 and develop a model of context defined by the structural similarities of phrases. We then apply this model to define measures of meaning in a corpus-guided experiment, computationally detecting entries missing from a massive, collaborative online dictionary known as the Wiktionary.
34
Praggastis, Brenda L. "Markov partitions for hyperbolic toral automorphisms /." Thesis, Connect to this title online; UW restricted, 1992. http://hdl.handle.net/1773/5773.
Full text
35
Vasylieva, Inna. "Very Cost Effective Partitions in Graphs." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1137.
Full textAbstract:
For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S.
A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.
36
León, Emerson [Verfasser]. "Spaces of convex n-partitions / Emerson León." Berlin : Freie Universität Berlin, 2015. http://d-nb.info/1069105600/34.
Full text
37
Lino, Christophe. "Virtual camera control using dynamic spatial partitions." Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00916835.
Full textAbstract:
Virtual camera control is nowadays an essential component in many computer graphics applications. Despite its importance, current approaches remain limited in their expressiveness, interactive nature and performances. Typically, elements of directorial style and genre cannot be easily modeled nor simulated due to the lack of simultaneous control in viewpoint computation, camera path planning and editing. Second, there is a lack in exploring the creative potential behind the coupling of a human with an intelligent system to assist users in the complex task of designing cinematographic sequences. Finally, most techniques are based on computationally expensive optimization techniques performed in a 6D search space, which prevents their application to real-time contexts. In this thesis, we first propose a unifying approach which handles four key aspects of cinematography (viewpoint computation, camera path planning, editing and visibility computation) in an expressive model which accounts for some elements of directorial style. We then propose a workflow allowing to combine automated intelligence with user interaction. We finally present a novel and efficient approach to virtual camera control which reduces the search space from 6D to 3D and has the potential to replace a number of existing formulations.
38
Heninger, Jeffrey M. "State Space Partitions of Stochastic Chaotic Maps." Thesis, Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/52117.
Full textAbstract:
The finest resolution that can be achieved in any real chaotic system is limited by the presence of noise. This noise can be used to define neighborhoods of the deterministic periodic orbits using the local eigenfunctions of the Fokker-Planck operator and its adjoint. We extend the work of D. Lippolis to include hyperbolic periodic orbits. The dynamics along the stable and unstable directions are separated. The neighborhoods on the stable and unstable manifolds can be defined in the same way as the neighborhoods for entirely stable or entirely unstable orbits. The neighborhoods are then returned to the original coordinates. The Fokker-Planck evolution can be described as a finite Markov transition graph between these neighborhoods. Its spectral determinant is used to calculate the time averages of observables. We apply this technique to calculate long time observables of the Lozi map.
39
Lee, Darren Vincent. "Some problems in the theory of partitions." Thesis, University of Nottingham, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.335468.
Full text
40
Pokrovskiy, Alexey. "Graph powers, partitions, and other extremal problems." Thesis, London School of Economics and Political Science (University of London), 2013. http://etheses.lse.ac.uk/754/.
Full textAbstract:
Graph theory is the study of networks of objects (called vertices) joined by links (called edges). Since many real world problems can be represented by a graph, graph theory has applications in areas such as sociology, chemistry, and computing. In this thesis, a number of open problems in graph theory are studied.
41
Kavanaugh, Joshua Stephen. "Dynamics of vacuum-sealed, double-leaf partitions." Thesis, The University of Alabama, 2016. http://pqdtopen.proquest.com/#viewpdf?dispub=10006857.
Full textAbstract:
The goal of this research is to investigate the feasibility and potential effectiveness of using vacuum-sealed, double-leaf partitions for applications in noise control. Substantial work has been done previously on double-leaf partitions where the acoustics of the inner chamber and mechanical vibrations of structural supports are passively and actively controlled. The work presented here is unique in that the proposed system aims to eliminate the need for active acoustic control of transmitted acoustic energy by removing all the air between the two panels of the double partition. Therefore, the only remaining energy paths would be along the boundary and at the points where there are intermediate structural supports connecting the two panels. The eventual goal of the research is to develop a high-loss double-leaf partition that simplifies active control by removing the need for control of the air cavity and channeling all the energy into discrete structural paths.
The work presented here is a first step towards the goal of designing a high-loss, actively-controlled double-leaf partition with an air-evacuated inner chamber. One experiment is conducted to investigate the effects of various levels of vacuum on the response of a double-leaf partition whose panels are mechanically coupled only at the boundary. Another experiment is conducted which investigates the effect of changing the stiffness of an intermediate support coupling the two panels of a double-leaf partition in which a vacuum has been applied to the inner cavity. The available equipment was able to maintain a 99% vacuum between the panels. Both experiments are accompanied by analytical models used to investigate the importance of various dynamic parameters. Results show that the vacuum-sealed system shows some potential for increased transmission loss, primarily by the changing the natural frequencies of the double-leaf partition.
42
RANDRIAMAHEFA, RAHERINAVALONA. "Contribution a la reconnaissance des partitions musicales." Paris 11, 1995. http://www.theses.fr/1995PA112192.
Full textAbstract:
Le contexte de cette etude est la reconnaissance des partitions musicales gravees. Le systeme qui a ete developpe comprend la reconnaissance des symboles musicaux suivants: notes, groupes de notes avec ou sans accord, differentes barres. Des solutions sont proposees pour la segmentation, c'est-a-dire la detection et l'effacement des lignes de portee, pour l'extraction des caracteristiques des symboles musicaux realisee a partir de leur squelette represente sous forme d'un graphe value, et pour la reconnaissance proprement dite. La phase de decision exploite une cooperation de plusieurs methodes: une methode analytique a partir du graphe, et des methodes basees sur la correlation et sur la projection utilisant une partie de l'image de la partition. La reconnaissance des notes se fait par l'intermediaire du graphe ; dans le cas d'un accord, l'approche basee sur la correlation est utilisee. L'originalite de ce systeme de reconnaissance repose sur l'exploitation du graphe et des retours en arriere sur l'image pour ameliorer la decision. De plus, des partitions complexes telles que des partitions a plusieurs voix ont ete analysees
43
Jacob, Jobby. "Variations on graph products and vertex partitions." Connect to this title online, 2009.
Find full text
44
Lamaison, Étienne Marie Joseph. "L´interprétation des partitions graphiques non-procédurales." Doctoral thesis, Universidade de Évora, 2013. http://hdl.handle.net/10174/11330.
Full textAbstract:
Résumé – Les partitions graphiques non-procédurales
Cette thèse examine quelles sont les ouvertures qui ont été offertes aux interprètes par l’avènement des partitions graphiques à partir des années 1950. Les partitions graphiques considérées sont désignées comme non-procédurales. Avec Nelson Goodman, il sera établi en quoi les partitions graphiques ne peuvent être considérées comme des formes notationnelles. Ce sont des musiques intuitives en ce sens qu’elles ne suivent pas une procédure d’exécution, mais invitent l’interprète à élaborer des processus de jeux. Après l’analyse de pièces comme celles d’Earle Brown ou de Cornelius Cardew seront dégagées diverses méthodologies d’interprétation des graphies sonores, proches de l’improvisation; Resumo - A interpretação das partituras gráficas não-procedimentais
Esta tese examina as aberturas oferecidas aos intérpretes com o advento das partituras gráficas, designadas como não-procedimentais, a partir dos anos 1950. Com Nelson Goodman, estabelece-se a razão dessas partituras gráficas não serem consideradas formas notacionais. São músicas intuitivas no sentido em que não seguem um procedimento de execução, mas convidam o intérprete a elaborar processos de jogo. Depois da análise de peças de Earle Brown ou Cornelieus Cardew esta tese propõe diversas metodologias de interpretação de grafias sonoras, próximas das utilizadas na improvisação; Abstract - The Interpretation of Non-Procedural Graphic Scores
This thesis examines the new possibilities offered to performers with the advent of graphic scores, called here non-procedural, from the 1950s onwards. Referring to Nelson Goodman, it establishes why these scores cannot be considered notational forms. Graphic scores are intuitive music in that they do not follow any procedure, but prompt the performer to develop processes of play. After analysing pieces by composers such as Earle Brown or Cornelius Cardew, this work proposes various methodologies for interpreting sonorous written forms, similar to those for improvisation.
45
Léna, Corentin. "Contributions à l'étude des partitions spectrales minimales." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00952556.
Full textAbstract:
Ce travail porte sur le problème des partitions minimales, à l'interface entre théorie spectrale et optimisation de forme. Une introduction générale précise le problème et présente des résultats, principalement dûs à B. Helffer, T. Hoffmann-Ostenhof et S. Terracini, qui sont utilisés dans le reste de la thèse.Le premier chapitre est une étude spectrale asymptotique du laplacien de Dirichlet sur une famille de domaines en dimension deux qui tend vers un segment. L'objectif est d'obtenir une localisation des lignes nodales dans la limite des domaines minces. En appliquant les résultats de Helffer, Hoffmann-Ostenhof et Terracini, on montre ainsi que les domaines nodaux des premières fonctions propres forment des partitions minimales.Le deuxième chapitre étudie les valeurs propres de certains opérateurs de Schrödinger sur un domaine plan avec condition au bord de Dirichlet. On considère des opérateurs qui ont un potentiel électrique nul et un potentiel magnétique d'un type particulier, dit d'Aharonov-Bohm, avec des singularités en un nombre fini de points appelés pôles. On démontre que les valeurs propres dépendent continuement des pôles. Dans le cas de pôles distincts et éloignés du bord, on prouve que cette dépendance est analytique lorsque la valeur propre est simple. On exprime de plus une condition suffisante pour que la fonction qui aux pôles associe une valeur propre présente un point critique. On utilise alors la caractérisation magnétique des partitions minimales pour montrer que l'énergie minimale est une valeur critique d'une de ces fonctions.Le troisième chapitre est un article écrit en collaboration avec Virginie Bonnaillie-Noël. Il porte sur une famille d'exemples, les secteurs angulaires de rayon unité et d'ouverture variable, dont on tente de déterminer les partitions minimales. On applique pour cela les théorèmes généraux rappelés dans l'introduction afin de déterminer les partitions nodales qui sont minimales. On s'intéresse plus particulièrement aux partitions minimales en trois domaines. En appliquant les idées du deuxième chapitre, on montre que pour certaines valeur de l'angle, il n'existe aucune partition minimale qui soit symétrique par rapport à la bissectrice du domaine. D'un point de vue quantitatif, on obtient des encadrements précis de l'énergie minimale.Le quatrième chapitre consiste en l'étude des partitions minimales de tores plats dont on fait varier le rapport entre longueur et largeur. On utilise une méthode numérique très différente de celle du troisième chapitre, basée sur un article de B. Bourdin, D. Bucur et É. Oudet. Elle consiste en une relaxation suivie d'une optimisation par un algorithme de gradient projeté. On peut ainsi tester des résultats théoriques antérieurs. Les résultats présentés suggèrent de plus la construction explicite de familles de partitions (en liaison avec des pavages du tore) qui donnent une nouvelle majoration de l'énergie minimale.Un dernier chapitre de perspectives présente plusieurs applications possibles des méthodes décrites dans la thèse.
46
Schacht, Mathias. "Regular partitions of hypergraphs and property testing." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2010. http://dx.doi.org/10.18452/13975.
Full textAbstract:
Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet.About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.
47
Elezi, Ismail <1991>. "Revealing Structure in Graphs Using Regular Partitions." Master's Degree Thesis, Università Ca' Foscari Venezia, 2016. http://hdl.handle.net/10579/7826.
Full textAbstract:
While originally introduced as a tool in proving a long-standing conjecture on arithmetic progressions, Szemeredi's regularity lemma has emerged over time as a fundamental tool in different branches of discrete mathematics and theoretical computer science. Roughly, it states that every graph can be approximated by the union of a small number of random-like bipartite graphs called regular pairs. In other words, the result provides us a way to obtain a good description of a large graph using a small amount of data, and can be regarded as a manifestation of the all-pervading dichotomy between structure and randomness.
However, the non-constructive nature of the lemma made its usefulness limited only in theoretical mathematics and computer science for around two decades. In the nineties, things changed when two different algorithmic versions of the lemma were developed, and by the end of last decade, the lemma was finally used in practice.
This thesis is a tentative to study the regularity lemma in context of structural pattern recognition. We will use the regularity lemma to compress some graph, and then study the reduced graph, knowing that it inherits the main properties of the original graph. By doing so, we will save both computer memory and CPU time.
48
Kasraoui, Anisse. "Études combinatoires sur les permutations et partitions d'ensemble." Phd thesis, Université Claude Bernard - Lyon I, 2009. http://tel.archives-ouvertes.fr/tel-00393631.
Full textAbstract:
Cette thèse regroupe plusieurs travaux de combinatoire énumérative sur les permutations et permutations d'ensemble. Elle comporte 4 parties.Dans la première partie, nous répondons aux conjectures de Steingrimsson sur les partitions ordonnées d'ensemble. Plus précisément, nous montrons que les statistiques de Steingrimsson sur les partitions ordonnées d'ensemble ont la distribution euler-mahonienne. Dans la deuxième partie, nous introduisons et étudions une nouvelle classe de statistiques sur les mots : les statistiques "maj-inv". Ces dernières sont des interpolations graphiques des célèbres statistiques "indice majeur" et "nombre d'inversions". Dans la troisième partie, nous montrons que la distribution conjointe des statistiques"nombre de croisements" et "nombre d'imbrications" sur les partitions d'ensemble est symétrique. Nous étendrons aussi ce dernier résultat dans le cadre beaucoup plus large des 01-remplissages de "polyominoes lunaires".La quatrième et dernière partie est consacrée à l'étude combinatoire des q-polynômes de Laguerre d'Al-Salam-Chihara. Nous donnerons une interprétation combinatoire de la suite de moments et des coefficients de linéarisations de ces polynômes.
49
Tomoda, Satoshi. "Partitions of unity in the theory of fibrations." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape15/PQDD_0002/MQ35002.pdf.
Full text
50
Mullen, Woodford Roger. "Partitions into prime powers and related divisor functions." Thesis, University of British Columbia, 2008. http://hdl.handle.net/2429/1246.
Full textAbstract:
In this thesis, we will study a class of divisor functions: the prime symmetric functions. These are polynomials over Q in the so-called elementary prime symmetric functions, whose values lie in Z. The latter are defined on the nonnegative integers and take the values of the elementary symmetric
functions applied to the multi-set of prime factors (with repetition) of an integer n.
Initially we look at basic properties of prime symmetric functions, and consider analogues of questions posed for the usual sum of proper divisors function, such as those concerning perfect numbers or Aliquot sequences. We consider the inverse question of when, and in how many ways a number $n$ can be expressed as f(m) for certain prime symmetric functions f. Then we look at asymptotic formulae for the average orders of certain fundamental prime symmetric functions, such as the arithmetic function whose value at n is the sum of k-th powers of the prime divisors (with repetition) of n.
For these last functions in particular, we also look at statistical results by comparing their distribution of values with the distribution of the largest prime factor dividing n.
In addition to average orders, we look at the modular distribution of prime symmetric functions, and show that for a fundamental class, they are uniformly distributed over any fixed modulus. Then our focus shifts to the related area of partitions into prime powers. We compute the appropriate asymptotic formulae, and demonstrate
important monotonicity properties.
We conclude by looking at iteration problems for some of the simpler prime symmetric functions. In doing so, we consider the empirical basis for certain conjectures, and are left with many open problems.