Dissertations / Theses on the topic 'Combinatorics'
To see the other types of publications on this topic, follow the link: Combinatorics.
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 'Combinatorics.'
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
Milicevic, Luka. "Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/273375.
Full text
2
Lopes, Martins Taísa. "Theory of combinatorial limits and extremal combinatorics." Thesis, University of Warwick, 2018. http://wrap.warwick.ac.uk/113462/.
Full textAbstract:
In the past years, techniques from different areas of mathematics have been successfully applied in extremal combinatorics problems. Examples include applications of number theory, geometry and group theory in Ramsey theory and analytical methods to different problems in extremal combinatorics. By providing an analytic point of view of many discrete problems, the theory of combinatorial limits led to substantial results in many areas of mathematics and computer science, in particular in extremal combinatorics. In this thesis, we explore the connection between combinatorial limits and extremal combinatorics. In particular, we prove that extremal graph theory problemsmay have unique optimal solutions with arbitrarily complex structure, study a property closely related to Sidorenko's conjecture, one of the most important open problems in extremal combinatorics, and prove a 30-year old conjecture of Gyori and Tuza regarding decomposing the edges of a graph into triangles and edges.
3
Yue, Guangyi. "Combinatorics of affine Springer fibers and combinatorial wall-crossing." Thesis, Massachusetts Institute of Technology, 2020. https://hdl.handle.net/1721.1/126939.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, May, 2020Cataloged from the official PDF of thesis.
Includes bibliographical references (pages 149-152).
This thesis deals with several combinatorial problems in representation theory. The first part of the thesis studies the combinatorics of affine Springer fibers of type A. In particular, we give an explicit description of irreducible components of Fl[subscript tS] and calculate the relative positions between two components. We also study the lowest two-sided Kazhdan-Lusztig cell and establish a connection with the affine Springer fibers, which is compatible with the affine matrix ball construction algorithm. The results also prove a special case of Lusztig's conjecture. The work in this part include joint work with Pablo Boixeda. In the second part, we define the combinatorial wall-crossing transformation and the generalized column regularization on partitions and prove that a certain composition of these two transformations has the same effect on the one-row partition. This result gives a special situation where column regularization, can be used to understand the complicated Mullineux map, and also proves a special case of Bezrukavnikov's conjecture. Furthermore, we prove a condition under which the two maps are exactly the same, generalizing the work of Bessenrodt, Olsson and Xu. The combinatorial constructions is related to the Iwahori-Hecke algebra and the global crystal basis of the basic [ ... ]-module and we provide several conjectures regarding the q-decomposition numbers and generalizations of results due to Fayers. This part is a joint work with Panagiotis Dimakis and Allen Wang.
by Guangyi Yue.
Ph. D.
Ph.D. Massachusetts Institute of Technology, Department of Mathematics
4
Lange, Carsten. "Combinatorial curvatures, group actions, and colourings: aspects of topological combinatorics." [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=973473487.
Full text
5
Engström, Alexander. "Topological Combinatorics." Doctoral thesis, KTH, Matematik (Inst.), 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-10383.
Full textAbstract:
This thesis on Topological Combinatorics contains 7 papers. All of them but paper Bare published before.In paper A we prove that!i dim ˜Hi(Ind(G);Q) ! |Ind(G[D])| for any graph G andits independence complex Ind(G), under the condition that G\D is a forest. We then use acorrespondence between the ground states with i+1 fermions of a supersymmetric latticemodel on G and ˜Hi(Ind(G);Q) to deal with some questions from theoretical physics.In paper B we generalize the topological Tverberg theorem. Call a graph on the samevertex set as a (d + 1)(q − 1)-simplex a (d, q)-Tverberg graph if for any map from thesimplex to Rd there are disjoint faces F1, F2, . . . , Fq whose images intersect and no twoadjacent vertices of the graph are in the same face. We prove that if d # 1, q # 2 is aprime power, and G is a graph on (d+1)(q −1)+1 vertices such that its maximal degreeD satisfy D(D + 1) < q, then G is a (d, q)–Tverberg graph. It was earlier known that thedisjoint unions of small complete graphs, paths, and cycles are Tverberg graphs.In paper C we study the connectivity of independence complexes. If G is a graphon n vertices with maximal degree d, then it is known that its independence complex is(cn/d + !)–connected with c = 1/2. We prove that if G is claw-free then c # 2/3.In paper D we study when complexes of directed trees are shellable and how one canglue together independence complexes for finding their homotopy type.In paper E we prove a conjecture by Björner arising in the study of simplicial polytopes.The face vector and the g–vector are related by a linear transformation. We prove thatthis matrix is totaly nonnegative. This is joint work with Michael Björklund.In paper F we introduce a generalization of Hom–complexes, called set partition complexes,and prove a connectivity theorem for them. This generalizes previous results ofBabson, Cukic, and Kozlov, and questions from Ramsey theory can be described with it.In paper G we use combinatorial topology to prove algebraic properties of edge ideals.The edge ideal of G is the Stanley-Reisner ideal of the independence complex of G. Thisis joint work with Anton Dochtermann.QC 20100712
6
Borenstein, Evan. "Additive stucture, rich lines, and exponential set-expansion." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/29664.
Full textAbstract:
Thesis (Ph.D)--Mathematics, Georgia Institute of Technology, 2009.Committee Chair: Croot, Ernie; Committee Member: Costello, Kevin; Committee Member: Lyall, Neil; Committee Member: Tetali, Prasad; Committee Member: Yu, XingXing. Part of the SMARTech Electronic Thesis and Dissertation Collection.
7
PINTO, RONALD COUTINHO. "INTRODUCTION TO COMBINATORICS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2014. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=24231@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROEste trabalho possui o intuito de desmistificar a dificuldade encontrada por professores e alunos no ensino e aprendizagem do tópico análise combinatória. A razão que motivou este trabalho foi o fato de que boa parte dos professores de matemática do ensino médio e últimas séries do ensino fundamental consideram a Análise Combinatória como algo complicado de ser ensinado; além da questão das dificuldades de entendimento por parte dos alunos que são induzidos à memorização de fórmulas e a aplicação das mesmas à resolução dos exercícios para compreenderem tal conteúdo. Inicialmente apresentaremos alguns conceitos que servirão como auxílio para que o professor possa trabalhar nas atividades propostas a serem desenvolvidas juntamente com os alunos. E ao longo do trabalho iremos falar de alguns tópicos abordados pela análise combinatória sem, inicialmente, mencionarmos fórmulas que servem apenas para serem memorizadas. O mais importante é fazer o aluno trabalhar um problema sugerido através do roteiro e dos conceitos que serão propostos e ao final de alguns exercícios, quando tal aluno tiver entendido tal conceito, ser anunciado a ele que acabou de aprender e entender o conceito em questão, ao invés de memorizar um determinado exercício ou outro, pois sabemos que desta forma, quando o aluno deparar-se com um novo problema, não será capaz de solucioná-lo. Dessa maneira, elaborou-se um roteiro na solução dos exercícios, ou seja, uma forma do professor trabalhar qualquer atividade proposta que envolva problemas de contagem em sala de aula. Enfim, buscou-se com esse trabalho, apresentar aos docentes, estratégias eficientes que podem ser utilizadas para o ensino de combinatória e ajudar os alunos a compreenderem melhor os problemas de contagem utilizando o raciocínio lógico e de contagem.
This work has the intent to explain the difficulties found by teachers and student on teaching and learning combinatorics. The motivation of this work was the fact that most of the Mathematics Teachers of High School consider combinatorics as something complicated to be taught; contributing as well the fact that students are led to memorize the formulas and apply it on exercises so they can understand the subject. Initially we will show some concepts that will help the Teachers to work together with the students on the proposed activities. During the work, we will talk about Combinatorics topics without mentioning formulas that needs memorization only. The most important thing is to make the student work on a suggested problem following a guide and concepts shown and after finishing a few exercises, when the student will show the understanding of the concepts, the Teacher will tell him that he learned that concept, instead of memorizing a specific exercise. Because we know that not doing this, when this student faces a new problem, he will not be able to solve it. Thus it was elaborated a guide to solve exercises and that means a way that the Teacher can work with any proposed activity that has counting in it. Finally, it was sought with this work to show the scholars some efficient strategies that can be used on teaching Combinatorics and help the students to understand better the problems about counting, using logical reasoning and logical counting.
8
Brunk, Fiona. "Intersection problems in combinatorics." Thesis, St Andrews, 2009. http://hdl.handle.net/10023/765.
Full text
9
Redelmeier, Daniel. "Hyperpfaffians in Algebraic Combinatorics." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1055.
Full textAbstract:
The pfaffian is a classical tool which can be regarded as a generalization of the determinant. The hyperpfaffian, which was introduced by Barvinok, generalizes the pfaffian to higher dimension. This was further developed by Luque, Thibon and Abdesselam. There are several non-equivalent definitions for the hyperpfaffian, which are discussed in the introduction of this thesis. Following this we examine the extension of the Matrix-Tree theorem to the Hyperpfaffian-Cactus theorem by Abdesselam, proving it without the use of the Grassman-Berezin Calculus and with the new terminology of the non-uniform hyperpfaffian. Next we look at the extension of pfaffian orientations for counting matchings on graphs to hyperpfaffian orientations for counting matchings on hypergraphs. Finally pfaffian rings and ideal s are extended to hyperpfaffian rings and ideals, but we show that under reason able assumptions the algebra with straightening law structure of these rings cannot be extended.
10
Sanders, Tom. "Topics in arithmetic combinatorics." Thesis, University of Cambridge, 2007. https://www.repository.cam.ac.uk/handle/1810/236994.
Full textAbstract:
This thesis is chiefly concerned with a classical conjecture of Littlewood's regarding the L¹-norm of the Fourier transform, and the closely related idem-potent theorem. The vast majority of the results regarding these problems are, in some sense, qualitative or at the very least infinitary and it has become increasingly apparent that a quantitative state of affairs is desirable. Broadly speaking, the first part of the thesis develops three new tools for tackling the problems above: We prove a new structural theorem for the spectrum of functions in A(G); we extend the notion of local Fourier analysis, pioneered by Bourgain, to a much more general structure, and localize Chang's classic structure theorem as well as our own spectral structure theorem; and we refine some aspects of Freiman's celebrated theorem regarding the structure of sets with small doubling. These tools lead to improvements in a number of existing additive results which we indicate, but for us the main purpose is in application to the analytic problems mentioned above. The second part of the thesis discusses a natural version of Littlewood's problem for finite abelian groups. Here the situation varies wildly with the underlying group and we pay special attention first to the finite field case (where we use Chang's Theorem) and then to the case of residues modulo a prime where we require our new local structure theorem for A(G). We complete the consideration of Littlewood's problem for finite abelian groups by using the local version of Chang's Theorem we have developed. Finally we deploy the Freiman tools along with the extended Fourier analytic techniques to yield a fully quantitative version of the idempotent theorem.
11
Green, B. "Topics in arithmetic combinatorics." Thesis, University of Cambridge, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.599660.
Full text
12
Mrazović, Rudi. "Topics in additive combinatorics." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:50d30d34-5b44-40f2-bb1a-98c2d81e6fe3.
Full textAbstract:
This thesis deals with four problems in additive combinatorics. After giving a brief introduction to the field and overview of the results in Chapter 1, in Chapter 2 we consider the problem of finding the clique number of the Cayley graph on 𝔽2n generated by a random subset. We prove a number of results, most notably that for n in a set of density 1, the clique number is concentrated on a single value. In Chapter 3 we prove that a randomly chosen subset of a finite group is a randomness extractor with high probability. More precisely, we prove that for every fixed δ > 0, given a finite group G and A ⊂ G a random subset of density 1/2, we prove that with high probability for all subsets |X| |Y| ≥ log2+δ |G| for ( 1/2 + o(1))|X| |Y| of the pairs (x; y) ∈ X × Y we have xy ∈ A. In Chapter 4 we give a new probabilistic model for the Paley graph which incorporates some multiplicative structure and as a result captures the Graham-Ringrose phenomenon, namely that the its clique number is sometimes a bit larger than what one might expect when considering the usual random model (random Cayley graph). We prove that if we sample such a random graph independently for every prime, then almost surely (i) for infinitely many primes p the clique number is Ω(log p log log p), whilst (ii) for almost all primes the clique number is (2 + o(1)) log p. Whereas in the previous chapters we were mostly concerned with generic sets, in Chapter 5 we consider a rather different problem concerning additive properties of a specific set. We prove an asymptotic for the number of additive triples of bijections {1,...,n} → ℤ=nℤ, that is, the number of pairs of bijections π1; π2: {1,...,n} → ℤ=nℤ such that the pointwise sum π1 + π2 is also a bijection.
13
Konvalinka, Matjaž. "Combinatorics of determinantal identities." Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/43790.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2008.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Includes bibliographical references (p. 125-129).
In this thesis, we apply combinatorial means for proving and generalizing classical determinantal identities. In Chapter 1, we present some historical background and discuss the algebraic framework we employ throughout the thesis. In Chapter 2, we construct a fundamental bijection between certain monomials that proves crucial for most of the results that follow. Chapter 3 studies the first, and possibly the best-known, determinantal identity, the matrix inverse formula, both in the commutative case and in some non-commutative settings (Cartier-Foata variables, right-quantum variables, and their weighted generalizations). We give linear-algebraic and (new) bijective proofs; the latter also give an extension of the Jacobi ratio theorem. Chapter 4 is dedicated to the celebrated MacMahon master theorem. We present numerous generalizations and applications. In Chapter 5, we study another important result, Sylvester's determinantal identity. We not only generalize it to non-commutative cases, we also find a surprising extension that also generalizes the master theorem. Chapter 6 has a slightly different, representation theory flavor; it involves representations of the symmetric group, and also Hecke algebras and their characters. We extend a result on immanants due to Goulden and Jackson to a quantum setting, and reprove certain combinatorial interpretations of the characters of Hecke algebras due to Ram and Remmel.
by Matjaž Konvalinka.
Ph.D.
14
Zhang, Yan Ph D. Massachusetts Institute of Technology. "The combinatorics of adinkras." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/84404.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Department of Mathematics, 2013.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 67-69).
Adinkras are graphical tools created to study representations of supersymmetry algebras. Besides having inherent interest for physicists, the study of adinkras has already shown nontrivial connections with coding theory and Clifford algebras. Furthermore, adinkras offer many easy-to-state and accessible mathematical problems of algebraic, combinatorial, and computational nature. In this work, we make a self-contained treatment of the mathematical foundations of adinkras that slightly generalizes the existing literature. Then, we make new connections to other areas including homological algebra, theory of polytopes, Pfaffian orientations, graph coloring, and poset theory. Selected results include the enumeration of odd dashings for all adinkraizable chromotopologies, the notion of Stiefel-Whitney classes for codes and their vanishing conditions, and the enumeration of all Hamming cube adinkras up through dimension 5.
by Yan Zhang.
Ph.D.
15
Mainetti, Matteo 1970. "Studies in projective combinatorics." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/47426.
Full text
16
Lam, Thomas F. (Thomas Fun Yau). "Combinatorics of ribbon tableaux." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/31166.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.Includes bibliographical references (p. 83-86).
This thesis begins with the study of a class of symmetric functions ... Which are generating functions for ribbon tableaux (hereon called ribbon functions), first defined by Lascoux, Leclerc and Thibon. Following work of Fomin and Greene, I introduce a set of operators called ribbon Schur operators on the space of partitions. I develop the theory of ribbon functions using these operators in an elementary manner. In particular, I deduce their symmetry and recover a theorem of Kashiwara, Miwa and Stern concerning the Fock space F of the quantum affine algebras ... Using these results, I study the functions ... in analogy with Schur functions, giving: * a Pieri and dual-Pieri formula for ribbon functions, * a ribbon Murnaghan-Nakayama formula, * ribbon Cauchy and dual Cauchy identities, * and a C-algebra isomorphism ... The study of the functions ... will be connected to the Fock space representation F of ...via a linear map [Iota]: F ... which sends the standard basis of F to the ribbon functions. Kashiwara, Miwa and Stern [29] have shown that a copy of the Heisenberg algebra H acts on F commuting with the action of ... Identifying the Fock Space of H with the ring of symmetric functions A(q) I will show that · is in fact a map of H-modules with remarkable properties. In the second part of the thesis, I give a combinatorial generalisation of the classical Boson-Fermion correspondence and explain how the map [phi] is an example of this more general phenomena. I show how certain properties of many families of symmetric functions arise naturally from representations of Heisenberg algebras. The main properties I consider are a tableaux-like definition, a Pieri-style rule and a Cauchy-style identity.
(cont.) Families of symmetric functions which can be viewed in this manner include Schur functions, Hall- Littlewood functions, Macdonald polynomials and the ribbon functions. Using work of Kashiwara, Miwa, Petersen and Yung, I define generalised ribbon functions for certain affine root systems 1 of classical type. I prove a theorem relating these generalised ribbon functions to a speculative global basis of level 1 q-deformed Fock spaces.
by Thomas F. Lam.
Ph.D.
17
Fiz, Pontiveros Gonzalo. "Topics in additive combinatorics." Thesis, University of Cambridge, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.608001.
Full text
18
Volec, Jan. "Analytic methods in combinatorics." Thesis, University of Warwick, 2014. http://wrap.warwick.ac.uk/71063/.
Full textAbstract:
In the thesis, we apply the methods from the recently emerged theory of limits of discrete structures to problems in extremal combinatorics. The main tool we use is the framework of ag algebras developed by Razborov. We determine the minimum threshold d that guarantees a 3-uniform hypergraph to contain four vertices which span at least three edges, if every linear-size subhypergraph of the hypergraph has density more than d. We prove that the threshold value d is equal to 1=4. The extremal configuration corresponds to the set of cyclically oriented triangles in a random orientation of a complete graph. This answers a question raised by Erdos. We also use the ag algebra framework to answer two questions from the extremal theory of permutations. We show that the minimum density of monotone subsequences of length �ve in any permutation is asymptotically equal to 1=256, and that the minimum density of monotone subsequences of length six is asymptotically equal to 1=3125. Furthermore, we characterize the set of (su�ciently large) extremal con�gurations for these two problems. Both the values and the characterizations of extremal con�gurations were conjectured by Myers. Flag algebras are also closely related to the theory of dense graph limits, where the main objects of study are convergent sequences of graphs. Such a sequence can be assigned an analytic object called a graphon. In this thesis, we focus on finitely forcible graphons. Those are graphons determined by �nitely many subgraph densities. We construct a �nitely forcible graphon such that the topological space of its typical vertices is not compact. In our construction, the space even fails to be locally compact. This disproves a conjecture of Lovasz and Szegedy.
19
Manners, Frederick. "Topics in additive combinatorics." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:96cd6439-ab33-41b5-be55-0aa5e8aad105.
Full text
20
Carroll, Christina C. "Enumerative combinatorics of posets." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/22659.
Full textAbstract:
Thesis (Ph. D.)--Mathematics, Georgia Institute of Technology, 2008.Committee Chair: Tetali, Prasad; Committee Member: Duke, Richard; Committee Member: Heitsch, Christine; Committee Member: Randall, Dana; Committee Member: Trotter, William T.
21
Johnson, Darin. "Topics in probabilistic combinatorics /." Available to subscribers only, 2009. http://proquest.umi.com/pqdweb?did=1879010731&sid=18&Fmt=2&clientId=1509&RQT=309&VName=PQD.
Full textAbstract:
Thesis (Ph. D.)--Southern Illinois University Carbondale, 2009."Department of Mathematics." Keywords: Kneser graphs, Probabilistic method, Random graphs, Rook numbers, Probabilistic combinatorics. Includes bibliographical references (p. 57-60). Also available online.
22
Johnson, Darin Bryant. "Topics In Probabilistic Combinatorics." OpenSIUC, 2009. https://opensiuc.lib.siu.edu/dissertations/63.
Full textAbstract:
This paper is a compilation of results in combinatorics utilizing the probabilistic method. Below is a brief description of the results highlighted in each chapter. Chapter 1 provides basic definitions, lemmas, and theorems from graph theory, asymptotic analysis, and probability which will be used throughout the paper. Chapter 2 introduces the independent domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the independent domination number is one of two values. Also, the the number of independent dominating sets of given cardinality is analyzed statistically. Chapter 3 introduces the tree domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the tree domination number is one of two values. Additional related domination parameters are also discussed. Chapter 4 introduces a generalized rook polynomial first studied by J. Goldman et al. Central and local limit theorems are then proven for certain classes of the generalized rook polynomial. Special cases include known central and local limit theorems for the Stirling numbers of the first and second kind and additionally new limit theorems for the Lah numbers and certain classes of known generalized Stirling numbers. Chapter 5 introduces the Kneser Graph. The exact expected value and variance of the distance between [n] and a vertex chosen uniformly at random is given. An asymptotic formula for the expectation is found.
23
Kim, Paul. "Rationalization of Combinatorial Design in Architecture for Microhousing." University of Cincinnati / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1491316065691636.
Full text
24
Carlier, Louis. "Objective combinatorics through decomposition spaces." Doctoral thesis, Universitat Autònoma de Barcelona, 2019. http://hdl.handle.net/10803/667374.
Full textAbstract:
Aquesta tesi proveeix construccions generals en el context d'espais de descomposici, generalitzant els resultats clàssics de la combinatòria al context homotòpic. Això requereix desenvolupar eines generals en la teoria d'espais de descomposició i noves perspectives, que siguin d'interès general, independentment de les aplicacions a la combinatòria.
Al primer capítol, resumim la teoria de l'homotopia i la combinatòria de la 2-categoria de grupoides. Continuem amb una revisió de les nocions necessàries de la teoria de categories d'ordre infinit. A continuació, resumim la teoria dels espais de descomposició.
Al segon capítol, identifiquem les estructures que tenen bi(co)mòduls d'incidència: són certs espais de Segal dobles augmentats subjectes a unes condicions d'exactitud. Establim un principi d'inversió de Möbius per a (co)mòduls i una fórmula de Rota per a certes estructures més implicades anomenades configuracions de bicomòduls de Möbius. La instància més important d'aquesta última noció sorgeix com cilindres d'aplicació d'adjuncions d'ordre infinit, o més generalment d'adjuncions entre espais de descomposició de Möbius, amb l'esperit de la fórmula original de Rota.
Al tercer capítol, presentem eines per proveir situacions en què s'aplica la fórmula generalitzada de Rota. Com a exemple, calculem la funció de Möbius de l'espai de descomposició dels conjunts parcialment ordenats finits i l'explotem per obtenir també una fórmula per a l'àlgebra d'incidència de qualsevol espècie de restricció dirigida, operad lliure, o més generalment monada lliure sobre una monada polinòmica finitària.
Al quart capítol, mostrem que les espècies hereditàries de Schmitt indueixen espais de descomposició monoidals i exhibim la construcció de biàlgebra de Schmitt com a instància de la construcció general de biàlgebra en un espai de descomposició monoidal. A més, mostrem que aquesta estructura de biàlgebra coactua sobre l'estructura de biàlgebra de les espècies restringides subjacent, per formar una biàlgebra en comòduls. Finalment, mostrem que les espècies hereditàries indueixen a una nova família d'exemples de categories operàdiques en el sentit de Batanin i Markl.
Al cinquè capítol, que representa un treball conjunt amb Joachim Kock, introduïm una noció d'antípoda per a espais de descomposició (complets) monoidals, que indueixen una noció d'antípoda feble per a les seves bialgebres d'incidència. En el cas connectat, recuperem la noció habitual d'antípoda per a les àlgebres de Hopf. En el cas no connectat expressa un principi d'inversió d'abast més limitat, però sempre suficient per calcular la funció de Möbius com μ = ζ ◦ S, tal com per a les àlgebres de Hopf. Al nivell de les espais de descomposició, l'antípoda feble pren la forma d'una diferència formal d'endofunctors lineals Seven − Sodd, i és un refinament de la construcció general d'inversió de Möbius de Gálvez–Kock–Tonks, però explotant l'estructura monoidal.This thesis provides general constructions in the context of decomposition spaces, generalising classical results from combinatorics to the homotopical setting. This requires developing general tools in the theory of decomposition spaces and new viewpoints, which are of general interest, independently of the applications to combinatorics. In the first chapter, we summarise the homotopy theory and combinatorics of the 2-category of groupoids. We continue with a review of needed notions from the theory of ∞-categories. We then summarise the theory of decomposition spaces. In the second chapter, we identify the structures that have incidence bi(co)modules: they are certain augmented double Segal spaces subject to some exactness conditions. We establish a Möbius inversion principle for (co)modules, and a Rota formula for certain more involved structures called Möbius bicomodule configurations. The most important instance of the latter notion arises as mapping cylinders of infinity adjunctions, or more generally of adjunctions between Möbius decomposition spaces, in the spirit of Rota’s original formula. In the third chapter, we present some tools for providing situations where the generalised Rota formula applies. As an example of this, we compute the Möbius function of the decomposition space of finite posets, and exploit this to derive also a formula for the incidence algebra of any directed restriction species, free operad, or more generally free monad on a finitary polynomial monad. In the fourth chapter, we show that Schmitt's hereditary species induce monoidal decomposition spaces, and exhibit Schmitt's bialgebra construction as an instance of the general bialgebra construction on a monoidal decomposition space. We show furthermore that this bialgebra structure coacts on the underlying restriction-species bialgebra structure so as to form a comodule bialgebra. Finally, we show that hereditary species induce a new family of examples of operadic categories in the sense of Batanin and Markl. In the fifth chapter, representing joint work with Joachim Kock, we introduce a notion of antipode for monoidal (complete) decomposition spaces, inducing a notion of weak antipode for their incidence bialgebras. In the connected case, this recovers the usual notion of antipode in Hopf algebras. In the non-connected case it expresses an inversion principle of more limited scope, but still sufficient to compute the Möbius function as μ = ζ ◦ S, just as in Hopf algebras. At the level of decomposition spaces, the weak antipode takes the form of a formal difference of linear endofunctors S_even - S_odd, and it is a refinement of the general Möbius inversion construction of Gálvez--Kock--Tonks, but exploiting the monoidal structure.
25
Larsson, David. "Combinatorics on Brauer-type semigroups." Thesis, Uppsala University, Department of Mathematics, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-121366.
Full text
26
Hilton, Jacob Haim. "Combinatorics of countable ordinal topologies." Thesis, University of Leeds, 2016. http://etheses.whiterose.ac.uk/13608/.
Full textAbstract:
We study combinatorial properties of ordinals under the order topology, focusing on the subspaces, partition properties and autohomeomorphism groups of countable ordinals. Our main results concern topological partition relations. Let n be a positive integer, let κ be a cardinal, and write [X] n for the set of subsets of X of size n. Given an ordinal β and ordinals αi for all i ∈ κ, write β →top (αi) n i∈κ to mean that for every function c : [β] n → κ (a colouring) there is some subspace X ⊆ β and some i ∈ κ such that X is homeomorphic to αi and [X] n ⊆ c −1 ({i}). We examine the cases n = 1 and n = 2, defining the topological pigeonhole number P top (αi) i∈κ to be the least ordinal β (when one exists) such that β →top (αi) 1 i∈κ , and the topological Ramsey number Rtop (αi) i∈κ to be the least ordinal β (when one exists) such that β →top (αi) 2 i∈κ . We resolve the case n = 1 by determining the topological pigeonhole number of an arbitrary sequence of ordinals, including an independence result for one class of cases. In the case n = 2, we prove a topological version of the Erd˝os–Milner theorem, namely that Rtop (α, k) is countable whenever α is countable and k is finite. More precisely, we prove that Rtop(ω ω β , k + 1) ≤ ω ω β·k for all countable ordinals β and all positive integers k. We also provide more careful upper bounds for certain small ordinals, including Rtop(ω + 1, k + 1) = ω k + 1, Rtop(α, k) < ωω whenever α < ω2 , Rtop(ω 2 , k) ≤ ω ω and Rtop(ω 2 + 1, k + 2) ≤ ω ω·k + 1 for all positive integers k. Outside the partition calculus, we prove a topological analogue of Hausdorff’s theorem on scattered total orderings. This allows us to characterise countable subspaces of ordinals as the order topologies of countable scattered total orderings. As an application, we compute the number of subspaces of an ordinal up to homeomorphism. Finally, we study the group of autohomeomorphisms of ω n ·m+1 for finite n and m. We classify the normal subgroups contained in the pointwise stabiliser of the limit points. These subgroups fall naturally into D (n) disjoint sets, each either countable or of size 22 ℵ0 , where D (n) is the number of ⊆-antichains of P ({1, 2, . . . , n}). Our techniques span a variety of disciplines, including set theory, general topology and permutation group theory.
27
Fiorini, Samuel. "Polyhedral combinatorics of order polytopes." Doctoral thesis, Universite Libre de Bruxelles, 2001. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211629.
Full text
28
Garner, David P. R. "Combinatorics and gauge-string duality." Thesis, Queen Mary, University of London, 2015. http://qmro.qmul.ac.uk/xmlui/handle/123456789/8939.
Full textAbstract:
This thesis exhibits a range of applications of combinatoric methods to string theory. The concepts and techniques used in the counting of ribbon graphs, the theory of finite groups, and the construction of cell complexes can give powerful methods and interesting insights into the nature of gauge-string duality, the limits of CFT factorisation, and the topology of worldsheet moduli space. The first part presents a candidate space-time theory of the Belyi string with a holographic extension to three-dimensional Euclidean gravity. This is a model of gauge-string duality in which the correlators of the Gaussian Hermitian matrix model are identfied with sums over worldsheet embeddings onto the 2-sphere target space. We show that the matrix model can be reformulated on the sphere by using su(2) representation couplings, and that the analogues of Feynman diagrams in this model can be holographically extended to 3-manifolds within the Ponzano-Regge model. The second part explores the limits of large N factorisation in conformal field theory and the dual interpretation in supergravity. By considering exact finite N correlators of single and multi-trace half-BPS operators in N = 4 super Yang-Mills theory in four dimensions, we can explicitly nd the exact threshold of the operator dimensions at which the correlators fail to factorise. In the dual supergravity, this is the energy regime at which quantum correlations between distinct gravitons become non-vanishing. The third part develops a cell decomposition of the moduli space of punctured Riemann surfaces. The cells are specified by a particular family of ribbon graphs, and we show that these graphs correspond to equivalence classes of permutation tuples arising from branched coverings of the Riemann sphere. This description yields efficient computational approaches for understanding the topology of moduli space.
29
Tenner, Bridget Eileen. "The combinatorics of reduced decompositions." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/34617.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006.Includes bibliographical references (p. 85-88) and index.
This thesis examines several aspects of reduced decompositions in finite Coxeter groups. Effort is primarily concentrated on the symmetric group, although some discussions are subsequently expanded to finite Coxeter groups of types B and D. In the symmetric group, the combined frameworks of permutation patterns and reduced decompositions are used to prove a new characterization of vexillary permutations. This characterization and the methods used yield a variety of new results about the structure of several objects relating to a permutation. These include its commutation classes, the corresponding graph of the classes, the zonotopal tilings of a particular polygon, and a poset defined in terms of these tilings. The class of freely braided permutations behaves particularly well, and its graphs and posets are explicitly determined. The Bruhat order for the symmetric group is examined, and the permutations with boolean principal order ideals are completely characterized. These form an order ideal which is a simplicial poset, and its rank generating function is computed. Moreover, it is determined when the set of permutations avoiding a particular set of patterns is an order ideal, and the rank generating functions of these ideals are computed.
(cont.) The structure of the intervals and order ideals in this poset is elucidated via patterns, including progress towards understanding the relationship between pattern containment and subintervals in principal order ideals. The final discussions of the thesis are on reduced decompositions in the finite Coxeter groups of types B and D. Reduced decompositions of the longest element in the hyperoctahedral group are studied, and expected values are calculated, expanding on previous work for the symmetric group. These expected values give a quantitative interpretation of the effects of the Coxeter relations on reduced decompositions of the longest element in this group. Finally, the Bruhat order in types B and D is studied, and the elements in these groups with boolean principal order ideals are characterized and enumerated by length.
by Bridget Eileen Tenner.
Ph.D.
30
Sam, Steven V. "Free resolutions, combinatorics, and geometry." Thesis, Massachusetts Institute of Technology, 2012. http://hdl.handle.net/1721.1/73178.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student submitted PDF version of thesis.
Includes bibliographical references (p. 71-72).
Boij-Söderberg theory is the study of two cones: the first is the cone of graded Betti tables over a polynomial ring, and the second is the cone of cohomology tables of coherent sheaves over projective space. Each cone has a triangulation induced from a certain partial order. Our first result gives a module-theoretic interpretation of this poset structure. The study of the cone of cohomology tables over an arbitrary polarized projective variety is closely related to the existence of an Ulrich sheaf, and our second result shows that such sheaves exist on the class of Schubert degeneracy loci. Finally, we consider the problem of classifying the possible ranks of Betti numbers for modules over a regular local ring.
by Steven V Sam.
Ph.D.
31
Ziegler, Günter M. (Günter Matthias). "Algebraic combinatorics of hyperplane arrangements." Thesis, Massachusetts Institute of Technology, 1987. http://hdl.handle.net/1721.1/14854.
Full text
32
Jeffers, Jason Adam. "Combinatorics and seifert knot invariants." Thesis, University of Cambridge, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.620418.
Full text
33
Baber, R. "Some results in extremal combinatorics." Thesis, University College London (University of London), 2011. http://discovery.ucl.ac.uk/1306175/.
Full textAbstract:
In Chapter 1 we determine the minimal density of triangles in a tripartite graph with prescribed edge densities. This extends work of Bondy, Shen, Thomassé and Thomassen characterizing those edge densities guaranteeing the existence of a triangle in a tripartite graph. We also determine those edge densities guaranteeing a copy of a triangle or C5 in a tripartite graph. In Chapter 2 we describe Razborov's flag algebra method and apply this to Erdös' jumping hypergraph problem to find the first non-trivial regions of jumps. We also use Razborov's method to prove five new sharp Turan densities, by looking at six vertex 3-graphs which are edge minimal and not 2-colourable. We extend Razborov's method to hypercubes. This allows us to significantly improve the upper bound given by Thomason and Wagner on the number of edges in a C4-free subgraph of the hypercube. We also show that the vertex Turan density of a 3-cube with a single vertex removed is precisely 3/4. In Chapter 3 we look at problems for intersecting families of sets on graphs. We give a new bound for the size of G-intersecting families on a cycle, disproving a conjecture of Johnson and Talbot. We also extend this result to cross-intersecting families and to powers of cycles. Finally in Chapter 4 we disprove a conjecture of Hurlbert and Kamat that the largest trivial intersecting family of independent r-sets from the vertex set of a tree is centred on a leaf.
34
Bloom, Thomas F. "Quantitative results in arithmetic combinatorics." Thesis, University of Bristol, 2014. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.678687.
Full textAbstract:
In this thesis we study the generalisation of Roth's theorem on three term arithmetic progressions to arbitrary discrete abelian groups and translation invariant linear equations. We prove a new structural result concerning sets of large Fourier coefficients and use this to prove new quantitative bounds on the size of finite sets which contain only trivial solutions to a given translation invariant linear equation. In particular, we obtain a quantitative improvement for Roth's theorem on three term arithmetic progressions and its analogue over lFq[t], the ring of polynomials in t with coefficients in a finite field Fq. We prove arithmetic inverse results for lFq[t] which characterise finite sets A such that IA + t . AI / IAI is small. In particular, when IA + AI « IAI we prove a quantitatively optimal result, which is the lFq[t]-analogue of the Polynomial Freiman-Ruzsa conjecture in the integers. In joint work with Timothy G. F. Jones we prove new sum-product estimates for finite subsets of lFq[t], and more generally for any local fields, such as Qp. We give an application of these estimates to exponential sums.
35
Jenssen, Matthew. "Continuous optimisation in extremal combinatorics." Thesis, London School of Economics and Political Science (University of London), 2017. http://etheses.lse.ac.uk/3572/.
Full textAbstract:
In this thesis we explore instances in which tools from continuous optimisation can be used to solve problems in extremal graph and hypergraph theory. We begin by introducing a generalised notion of hypergraph Lagrangian and use tools from the theory of nonlinear optimisation to explore some of its properties. As an application we find the Tur´an density of a small family of hypergraphs. We determine the exact k-colour Ramsey number of an odd cycle on n vertices when n is large. This resolves a conjecture of Bondy and Erd˝os for large n. The first step of our proof is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. We establish a correspondence between extremal constructions in the Ramsey setting and optimal points in the continuous setting. We thereby uncover a correspondence between extremal constructions and perfect matchings in the k-dimensional hypercube. This allows us to prove a stability type result around these extremal constructions. We consider two models from statistical physics, the hard-core model and the monomer-dimer model. Using tools from linear programming we give tight upper bounds on the logarithmic derivative of the independence and matching polynomials of a d-regular graph. For independent sets, this is a strengthening of a sequence of results of Kahn, Galvin and Tetali, and Zhao that a disjoint union of Kd,d’s maximises the independence polynomial and total number of independent sets among all d-regular graphs on the same number of vertices. For matchings, the result implies that disjoint unions of Kd,d’s also maximise the matching polynomial and total number of matchings. Moreover we prove the Asymptotic Upper Matching Conjecture of Friedland, Krop, Lundow, and Markstr¨om. Through our study of the hard-core model, we also prove lower bounds on the average size and the number of independent sets in a triangle-free graph of maximum degree d. As a consequence we obtain a new proof of Shearer’s celebrated upper bound on the Ramsey number R(3, k).
36
David, Stefan. "Extremal combinatorics and universal algorithms." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/278254.
Full textAbstract:
In this dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we focus on some new automata that do not seem to have occurred much in the literature, that of solvability of mazes. For our model, a maze is a countable strongly connected digraph together with a proper colouring of its edges (without two edges leaving a vertex getting the same colour) and two special vertices: the origin and the destination. A pointer or robot starts in the origin of a maze and moves naturally between its vertices, according to a sequence of specific instructions from the set of all colours; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. We call such a finite or infinite sequence of instructions an algorithm. In particular, one of the most interesting and very natural sets of mazes occurs when our maze is the square lattice Z2 as a graph with some of its edges removed. Obviously, we need to require that the origin and the destination vertices are in the same connected component and it is very natural to take the four instructions to be the cardinal directions. In this set-up, we make progress towards a beautiful problem posed by Leader and Spink in 2011 which asks whether there is an algorithm which solves the set of all such mazes. Next, we address a problem regarding symmetric chain decompositions of posets. We ask if there exists a symmetric chain decomposition of a 2 × 2 × ... × 2 × n cuboid (k 2’s) such that no chain has a subchain of the form (a1,...,ak,0) ≺ ... ≺ (a1,...,ak,n−1)? We show this is true precisely when k≥5 and n≥3. Thisquestion arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this chapter unexpectedly resolves the most difficult case of previous work by Spink on almost orthogonal symmetric chain decompositions (2017) which makes progress on a conjecture of Shearer and Kleitman. Moreover, we generalize our methods to other finite graded posets. Finally, we address two different problems in extremal combinatorics related to mathematical physics. Firstly, we study metastable states in the Ising model. We propose a general model for 1-flip spin systems, and initiate the study of extremal properties of their stable states. By translating local stability conditions into Sperner- type conditions, we provide non-trivial upper bounds which are often tight for large classes of such systems. The last topic we consider is a deterministic bootstrap percolation type problem. More specifically, we prove several extremal results about fast 2-neighbour percolation on the two dimensional grid.
37
Woodcock, David J. "Schur algebras, combinatorics, and cohomology." Thesis, University of Warwick, 1991. http://wrap.warwick.ac.uk/108093/.
Full textAbstract:
Let G = GLn(k), the group of all invertible n x n matrices over an infinite field k. In this thesis we explore the cohomological relationship between a Schur algebra S(G) for G and the subalgebra S(B) corresponding to a Borel subgroup B of G. Our main motivation is the question of whether there is an analogue of the Kempf Vanishing Theorem in this setting. We place our study in a more general framework, defining subalgebras S(Ω,Г) of S(G) associated with certain intersections of parabolic subgroups of G, and investigate the connection between S(Ω,Г) and the subalgebra S(S(Ω,Ø). We define modules for S(Ω,Г) which serve as analogues for the Weyl modules for S(G). We produce bases for these Weyl modules and thereby show that S(Ω,Г) is a quasi- hereditary algebra. We find two-step projective presentations for the Weyl modules over subalgebras S(Ω,Г) of S(Ω,Г). and in special cases find projective resolutions. We use these to prove results which provide partial information on the existence of an analogue for the Kempf Vanishing Theorem, and on related questions. We derive a character formula for the Weyl modules which can be regarded as an extension of the Jacobi-Trudi identity for Schur functions. The methods used in this thesis are in the main elementary, with a heavy reliance on direct combinatorial arguments.
38
Nemati, Navid. "Syzygies : algebra, combinatorics and geometry." Thesis, Sorbonne université, 2019. http://www.theses.fr/2019SORUS284.
Full textAbstract:
La régularité de Castelnuovo-Mumford est l'un des principaux invariants numériques permettant de mesurer la complexité de la structure des modules gradués de type fini sur des anneaux polynomiaux. Il mesure le degré maximal des générateurs des modules de syzygies. Dans cette thèse, nous étudions la régularité de Castelnuovo-Mumford avec différents points de vue et, dans certaines parties, nous nous concentrons principalement sur les syzygies linéaires. Dans le chapitre 2, nous étudions la régularité des homologies de Koszul et des cycles de Koszul de quotients unidimensionnels. Dans le chapitre 3, nous étudions les propriétés de Lefschetz faibles et fortes d'une classe d'idéaux monomiaux artiniens. Nous donnons, dans certains cas, une réponse affirmative à une conjecture d'Eisenbud, Huneke et Ulrich. Dans les chapitres 4 et 5, nous étudions deux comportements asymptotiques différents de la régularité de Castelnuovo-Mumford. Dans le chapitre 4, nous travaillons sur un quotient d'une algèbre noethérienne standard par suite régulière homogène. Au chapitre 5, nous étudions la régularité des puissances des idéaux monomiaux associés aux graphes en haltère. Dans le chapitre 6, nous travaillons sur des espaces projectifs. Au début de ce chapitre, nous présentons un package pour le logiciel informatique Macaulay2. De plus, nous étudions les cohomologies des "intersections complètes" dans Pnx PmCastelnuovo-Mumford regularity is one of the main numerical invariants that measure the complexity of the structure of homogeneous finitely generated modules over polynomial rings. It measures the maximum degrees of generators of the syzygies. In this thesis we study the Castelnuovo-Mumford regularity with different points of view and, in some parts, we mainly focus on linear syzygies. In Chapter 2 we study the regularity of Koszul homologies and Koszul cycles of one dimensional quotients. In Chapter 3 we study the weak and strong Lefschetz properties of a class of artinain monomial ideals. We show how the structure of the minimal free resolution could force weak or strong Lefschetz properties. In Chapter 4 and 5we study two different asymptotic behavior of Castelnuovo-Mumford regularity. In Chapter 4 we work on a quotient of a standard graded Noetherian algebra by homogeneous regular sequence. It is a celebrated result that the regularity of powers of an ideal in a polynomial ring becomes a linear function. In Chapter 5, we study the regularity of powers of dumbbell graphs. In Chapter 6, we work on product of projective spaces. In the begining of this chapter, we present a package for the computer software Macaulay2. Furthermore, we study the cohomologies of the “complete intersections'' in Pn x Pm
39
Ahmed, Maya. "Algebraic combinatorics of magic squares /." For electronic version search Digital dissertations database. Restricted to UC campuses. Access is free to UC campus dissertations, 2004. http://uclibs.org/PID/11984.
Full text
40
Saigo, Hayato. "From Combinatorics to Noncommutative Probability." 京都大学 (Kyoto University), 2011. http://hdl.handle.net/2433/142351.
Full text
41
Han, Bin. "Gamma positivity in enumerative combinatorics." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1115/document.
Full textAbstract:
La positivité gamma d’une suite combinatoire unifie à la fois l’unimodalité et la symétrie de cette suite. Trouver des nouvelles familles d’objets dont les polynômes énumératives ont une positivité gamma est un défi et un sujet important en combinatoire et géométrie. Il a attiré beaucoup d’attention ces derniers temps en raison de la conjecture de Gal, qui affirme que le gamma-vecteur a des coefficients positifs pour n’importe quel polytope simple. Souvent, le h-polynôme pour les polytopes simpliciaux de signification combinatoire peut être donné en tant que fonction génératrice sur un ensemble d’objets combinatoires apparentés par rapport à une statistique telle que le nombre des descentes, dont les polynômes énumératifs sur les permutations sont des polynômes Eulériens. Ce travail traite des propriétés gamma de plusieurs polynômes énumératifs de permutations tels que les polynômes Eulériens et les polynômes de Narayana. Cette thèse contient cinq chapitresThe gamma positivity of a combinatorial sequence unifies both unimodality and symmetry. Finding new family of objets whose enumerative sequences have gamma positivity is a challenge and important topic in recent years. it has received considerable attention in recent times because of Gal’s conjecture, which asserts that the gamma-vector has nonnegative entries for any flag simple polytope. Often times, the h-polynomial for simplicial polytopes of combinatorial signification can be given as a generating function over a related set of combinatorial objects with respect to some statistic like the descent numbers, whose enumerative polynomials on permutations are Eulerian polynomials.This work deals with the gamma properties of several enumerative polynomials of permutation such as Eulerian polynomials and Narayana polynomials. This thesis contains five chapters
42
Brignall, Robert. "Simplicity in relational structures and its application to permutation classes." Thesis, St Andrews, 2007. http://hdl.handle.net/10023/431.
Full text
43
Spiegel, Christoph. "Additive structures and randomness in combinatorics." Doctoral thesis, Universitat Politècnica de Catalunya, 2020. http://hdl.handle.net/10803/669327.
Full textAbstract:
Arithmetic Combinatorics, Combinatorial Number Theory, Structural Additive Theory and Additive Number Theory are just some of the terms used to describe the vast field that sits at the intersection of Number Theory and Combinatorics and which will be the focus of this thesis. Its contents are divided into two main parts, each containing several thematically related results.
The first part deals with the question under what circumstances solutions to arbitrary linear systems of equations usually occur in combinatorial structures..The properties we will be interested in studying in this part relate to the solutions to linear systems of equations.
A first question one might ask concerns the point at which sets of a given size will typically contain a solution. We will establish a threshold and also study the distribution of the number of solutions at that threshold, showing that it converges to a Poisson distribution in certain cases.
Next, Van der Waerden’s Theorem, stating that every finite coloring of the integers contains monochromatic arithmetic progression of arbitrary length, is by some considered to be the first result in Ramsey Theory. Rado generalized van der Waerden’s result by characterizing those linear systems whose solutions satisfy a similar property and Szemerédi strengthened it to a statement concerning density rather than colorings. We will turn our attention towards versions of Rado’s and Szemerédi’s Theorem in random sets, extending previous work of Friedgut, Rödl, Rucin´ski and Schacht in the case of the former and of Conlon, Gowers and Schacht for the latter to include a larger variety of systems and solutions.
Lastly, Chvátal and Erdo¿s suggested studying Maker-Breaker games. These games have deep connections to the theory of random structures and we will build on work of Bednarska and Luczak to establish the threshold for how much a large variety of games need to be biased in favor of the second player. These include games in which the first player wants to occupy a solution to some given linear system, generalizing the van der Waerden games introduced by Beck.
The second part deals with the extremal behavior of sets with interesting additive properties. In particular, we will be interested in bounds or structural descriptions for sets exhibiting some restrictions with regards to either their representation function or their sumset.
First, we will consider Sidon sets, that is sets of integers with pairwise unique differences. We will study a generalization of Sidon sets proposed very recently by Kohayakawa, Lee, Moreira and Rödl, where the pairwise differences are not just distinct, but in fact far apart by a certain measure. We will obtain strong lower bounds for such infinite sets using an approach of Cilleruelo. As a consequence of these bounds, we will also obtain the best current lower bound for Sidon sets in randomly generated infinite sets of integers of high density.
Next, one of the central results at the intersection of Combinatorics and Number Theory is the Freiman–Ruzsa Theorem stating that any finite set of integers of given doubling can be efficiently covered by a generalized arithmetic progression. In the case of particularly small doubling, more precise structural descriptions exist. We will first study results going beyond Freiman’s well-known 3k–4 Theorem in the integers. We will then see an application of these results to sets of small doubling in finite cyclic groups.
Lastly, we will turn our attention towards sets with near-constant representation functions. Erdo¿s and Fuchs established that representation functions of arbitrary sets of integers cannot be too close to being constant. We will first extend the result of Erdo¿s and Fuchs to ordered representation functions. We will then address a related question of Sárközy and Sós regarding weighted representation function.La combinatòria aritmètica, la teoria combinatòria dels nombres, la teoria additiva estructural i la teoria additiva de nombres són alguns dels termes que es fan servir per descriure una branca extensa i activa que es troba en la intersecció de la teoria de nombres i de la combinatòria, i que serà el motiu d'aquesta tesi doctoral. La primera part tracta la qüestió de sota quines circumstàncies es solen produir solucions a sistemes lineals d’equacions arbitràries en estructures additives. Una primera pregunta que s'estudia es refereix al punt en que conjunts d’una mida determinada contindran normalment una solució. Establirem un llindar i estudiarem també la distribució del nombre de solucions en aquest llindar, tot demostrant que en certs casos aquesta distribució convergeix a una distribució de Poisson. El següent tema de la tesis es relaciona amb el teorema de Van der Waerden, que afirma que cada coloració finita dels nombres enters conté una progressió aritmètica monocromàtica de longitud arbitrària. Aquest es considera el primer resultat en la teoria de Ramsey. Rado va generalitzar el resultat de van der Waerden tot caracteritzant en aquells sistemes lineals les solucions de les quals satisfan una propietat similar i Szemerédi la va reforçar amb una versió de densitat del resultat. Centrarem la nostra atenció cap a versions del teorema de Rado i Szemerédi en conjunts aleatoris, ampliant els treballs anteriors de Friedgut, Rödl, Rucinski i Schacht i de Conlon, Gowers i Schacht. Per últim, Chvátal i Erdos van suggerir estudiar estudiar jocs posicionals del tipus Maker-Breaker. Aquests jocs tenen una connexió profunda amb la teoria de les estructures aleatòries i ens basarem en el treball de Bednarska i Luczak per establir el llindar de la quantitat que necessitem per analitzar una gran varietat de jocs en favor del segon jugador. S'inclouen jocs en què el primer jugador vol ocupar una solució d'un sistema lineal d'equacions donat, generalitzant els jocs de van der Waerden introduïts per Beck. La segona part de la tesis tracta sobre el comportament extrem dels conjunts amb propietats additives interessants. Primer, considerarem els conjunts de Sidon, és a dir, conjunts d’enters amb diferències úniques quan es consideren parelles d'elements. Estudiarem una generalització dels conjunts de Sidons proposats recentment per Kohayakawa, Lee, Moreira i Rödl, en que les diferències entre parelles no són només diferents, sinó que, en realitat, estan allunyades una certa proporció en relació a l'element més gran. Obtindrem límits més baixos per a conjunts infinits que els obtinguts pels anteriors autors tot usant una construcció de conjunts de Sidon infinits deguda a Cilleruelo. Com a conseqüència d'aquests límits, obtindrem també el millor límit inferior actual per als conjunts de Sidon en conjunts infinits generats aleatòriament de nombres enters d'alta densitat. A continuació, un dels resultats centrals a la intersecció de la combinatòria i la teoria dels nombres és el teorema de Freiman-Ruzsa, que afirma que el conjunt suma d'un conjunt finit d’enters donats pot ser cobert de manera eficient per una progressió aritmètica generalitzada. En el cas de que el conjunt suma sigui de mida petita, existeixen descripcions estructurals més precises. Primer estudiarem els resultats que van més enllà del conegut teorema de Freiman 3k-4 en els enters. Llavors veurem una aplicació d’aquests resultats a conjunts de dobles petits en grups cíclics finits. Finalment, dirigirem l’atenció cap a conjunts amb funcions de representació gairebé constants. Erdos i Fuchs van establir que les funcions de representació de conjunts arbitraris d’enters no poden estar massa a prop de ser constants. Primer estendrem el resultat d’Erdos i Fuchs a funcions de representació ordenades. A continuació, abordarem una pregunta relacionada de Sárközy i Sós sobre funció de representació ponderada.
44
Eriksen, Niklas. "Combinatorics of genome rearrangements and phylogeny." Licentiate thesis, KTH, Mathematics, 2001. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-1499.
Full textAbstract:
This thesis deals with combinatorial problems taken frombioinformatics. In particular, we study the problem ofinferring distances between bacterial species by looking attheir respective gene orders. We regard one of the gene ordersas a permutation of the other. Given a set of valid operations,we seek the most parsimonious way to sort this permutation. Wealso look at the more complex problem of combining a set ofspecies into a phylogenetic tree, which shows the relationshipsbetween all species.The computer program Derange II by Blanchette andSanko® uses a greedy algorithm to estimate theevolutionary distance between two species. The success dependson a set of weights, which may be specified by the user. Wehave examined which weights are optimal, and also the qualityof this program using optimal weights.Derange II has been extended to solve the medianproblem, that is finding the permutation that is closest tothree other permutations. We then use this new version to buildphylogenetic trees directly from gene order permutations. Insome situations, this new method works much better thanprevious methods.There is an analytical expression for the evolutionarydistance between two species if the set of allowed operationsincludes only inversions (reversing a segment of genes).Allowing transpositions (swapping two adjacent segments) aswell, we have found a (1+")-approximation for this distance,where we have weighted the di®erent operations accordingto our results on the Derange II weights.
45
Modan, Laurentiu. "TO TEACH COMBINATORICS, USING SELECTED PROBLEMS." Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-80681.
Full textAbstract:
In 1972, professor Grigore Moisil, the most famous Romanian academician for Mathematics, said about Combinatorics, that it is “an opportunity of a renewed gladness”, because “each problem in the domain asks for its solving, an expenditure without any economy of the human intelligence”. More, the research methods, used in Combinatorics, are different from a problem to the other! This is the explanation for the existence of my actual paper, in which I propose to teach Combinatorics, using selected problems. MS classification: 05A05, 97D50.
46
Sjöstrand, Jonas. "Enumerative combinatorics related to partition shapes." Doctoral thesis, KTH, Matematik (Inst.), 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4298.
Full textAbstract:
This thesis deals with enumerative combinatorics applied to three different objects related to partition shapes, namely tableaux, restricted words, and Bruhat intervals. The main scientific contributions are the following. Paper I: Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^[n/2]. We prove a generalisation of this conjecture using the Robinson-Schensted correspondence and a new concept called chess tableaux. The proof is built on a remarkably simple relation between the sign of a permutation pi and the signs of its RS-corresponding tableaux P and Q, namely sgn(pi) = (−1)^v sgn(P)sgn(Q), where v is the number of disjoint vertical dominoes that fit in the partition shape of P and Q. The sign-imbalance of a partition shape is defined as the sum of the signs of all standard Young tableaux of that shape. As a further application of the sign-transferring formula above, we also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. Paper II: We generalise some of the results in paper I to skew tableaux. More precisely, we examine how the sign property is transferred by the skew Robinson-Schensted correspondence invented by Sagan and Stanley. The result is a surprisingly simple generalisation of the ordinary non-skew formula above. As an application, we find vanishing weighted sums of squares of sign-imbalances, thereby generalising a variant of Stanley’s second conjecture. Paper III: The following special case of a conjecture by Loehr and Warrington was proved by Ekhad, Vatter, and Zeilberger: There are 10^n zero-sum words of length 5n in the alphabet {+3,−2} such that no consecutive subword begins with +3, ends with −2, and sums to −2. We give a simple bijective proof of the conjecture in its original and more general setting where 3 and 2 are replaced by any relatively prime positive integers a and b, 10^n is replaced by ((a+b) choose a)^n, and 5n is replaced by (a+b)n. To do this we reformulate the problem in terms of cylindrical lattice walks which can be interpreted as the south-east border of certain partition shapes. Paper IV: We characterise the permutations pi such that the elements in the closed lower Bruhat interval [id,pi] of the symmetric group correspond to non-capturing rook configurations on a skew Ferrers board. These intervals turn out to be exactly those whose flag manifolds are defined by inclusions, as defined by Gasharov and Reiner. The characterisation connects Poincaré polynomials (rank-generating functions) of Bruhat intervals with q-rook polynomials, and we are able to compute the Poincaré polynomial of some particularly interesting intervals in the finite Weyl groups A_n and B_n. The expressions involve q-Stirling numbers of the second kind, and for the group A_n putting q = 1 yields the poly-Bernoulli numbers defined by Kaneko.Ämnet för denna avhandling är enumerativ kombinatorik tillämpad på tre olika objekt med anknytning till partitionsformer, nämligen tablåer, begränsade ord och bruhatintervall. Dom viktigaste vetenskapliga bidragen är följande. Artikel I: Låt tecknet av en standardtablå vara tecknet hos permutationen man får om man läser tablån rad för rad från vänster till höger, som en bok. En förmodan av Richard Stanley säjer att teckensumman av alla standardtablåer med n rutor är 2^[n/2]. Vi visar en generalisering av denna förmodan med hjälp av Robinson-Schensted-korrespondensen och ett nytt begrepp som vi kallar schacktablåer. Beviset bygger på ett anmärkningsvärt enkelt samband mellan tecknet hos en permutation pi och tecknen hos dess RS-motsvarande tablåer P och Q, nämligen sgn(pi)=(-1)^v sgn(P)sgn(Q), där v är antalet disjunkta vertikala dominobrickor som får plats i partitionsformen hos P och Q. Teckenobalansen hos en partitionsform definieras som teckensumman av alla standardtablåer av den formen. Som en ytterligare tillämpning av formeln för teckenöverföring ovan bevisar vi också en starkare variant av en annan förmodan av Stanley som handlar om viktade summor av kvadrerade teckenobalanser. Artikel II: Vi generaliserar några av resultaten i artikel I till skeva tablåer. Närmare bestämt undersöker vi hur teckenegenskapen överförs av Sagan och Stanleys skeva Robinson-Schensted-korrespondens. Resultatet är en förvånansvärt enkel generalisering av den vanliga ickeskeva formeln ovan. Som en tillämpning visar vi att vissa viktade summor av kvadrerade teckenobalanser blir noll, vilket leder till en generalisering av en variant av Stanleys andra förmodan. Artikel III: Följande specialfall av en förmodan av Loehr och Warrington bevisades av Ekhad, Vatter och Zeilberger: Det finns 10^n ord med summan noll av längd 5n i alfabetet {+3,-2} sådana att inget sammanhängande delord börjar med +3, slutar med -2 och har summan -2. Vi ger ett enkelt bevis för denna förmodan i dess ursprungliga allmännare utförande där 3 och 2 byts ut mot vilka som helst relativt prima positiva heltal a och b, 10^n byts ut mot ((a+b) över a)^n och 5n mot (a+b)n. För att göra detta formulerar vi problemet i termer av cylindriska latticestigar som kan tolkas som den sydöstra gränslinjen för vissa partitionsformer. Artikel IV: Vi karakteriserar dom permutationer pi sådana att elementen i det slutna bruhatintervallet [id,pi] i symmetriska gruppen motsvarar ickeslående tornplaceringar på ett skevt ferrersbräde. Dessa intervall visar sej vara precis dom vars flaggmångfalder är definierade av inklusioner, ett begrepp introducerat av Gasharov och Reiner. Karakteriseringen skapar en länk mellan poincarépolynom (ranggenererande funktioner) för bruhatintervall och q-tornpolynom, och vi kan beräkna poincarépolynomet för några särskilt intressanta intervall i dom ändliga weylgrupperna A_n och B_n. Uttrycken innehåller q-stirlingtal av andra sorten, och sätter man q=1 för grupp A_n så får man Kanekos poly-bernoullital.
QC 20100818
47
Samieinia, Shiva. "Digital Geometry, Combinatorics, and Discrete Optimization." Doctoral thesis, Stockholms universitet, Matematiska institutionen, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-47399.
Full textAbstract:
This thesis consists of two parts: digital geometry and discrete optimization. In the first part we study the structure of digital straight line segments. We also study digital curves from a combinatorial point of view. In Paper I we study the straightness in the 8-connected plane and in the Khalimsky plane by considering vertical distances and unions of two segments. We show that we can investigate the straightness of Khalimsky arcs by using our knowledge from the 8-connected plane. In Paper II we determine the number of Khalimsky-continuous functions with 2, 3 and 4 points in their codomain. These enumerations yield examples of known sequences as well as new ones. We also study the asymptotic behavior of each of them. In Paper III we study the number of Khalimsky-continuous functions with codomain Z and N. This gives us examples of Schröder and Delannoy numbers. As a byproduct we get some relations between these numbers. In Paper IV we study the number of Khalimsky-continuous functions between two points in a rectangle. Using a generating function we get a recurrence formula yielding this numbers. In the second part we study an analogue of discrete convexity, namely lateral convexity. In Paper V we define by means of difference operators the class of lateral convexity. The functions have plus infinity in their codomain. For the real-valued functions we need to check the difference operators for a smaller number of points. We study the relation between this class and integral convexity. In Paper VI we study the marginal function of real-valued functions in this class and its generalization. We show that for two points with a certain distance we have a Lipschitz property for the points where the infimum is attained. We show that if a function is in this class, the marginal function is also in the same class.At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 4: Submitted. Paper 5: Manuscript. Paper 6: Manuscript.
48
Saevarsson, Freyr. "Combinatorics in Pattern-Based Graphical Passwords." Thesis, KTH, Matematik (Inst.), 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-102004.
Full textAbstract:
Because of increased computing power it is necessary for modern passwords to be very long and complex, this makes them hard to remember. Research show that it might be easier for people to remember visual passwords instead of textual ones. The goal of this project was to find a safe graphical password scheme which does not require any modification on the server side. A proposed solution is called the Abagram which is a system that transforms patterns on a grid into textual passwords. The main idea behind the scheme is to assign each cell in the grid a letter or a symbol. The users select some cells by passing their finger over them. The password becomes the letters of the cells in the order in which they are passed. The thesis consists of a study of the combinatorics of user-selected patterns, a theoretical security analysis of the Abagram, an analysis of a user study constructed for Android smartphones and methods for evaluating the strenght of a given pattern. The Abagram does show promise, an average pattern from the study suggest a password space with entropy of about 68 bits which is comparable with a random 10 digit password. The Abagram might be especially useful when used with a smartphone but there are still some usability and implementation aspects which must be analysed further
49
Tateno, Atsushi. "Problems in finite and infinite combinatorics." Thesis, University of Oxford, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.504612.
Full text
50
Bandlow, Jason. "Combinatorics of Macdonald polynomials and extensions." Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2007. http://wwwlib.umi.com/cr/ucsd/fullcit?p3259066.
Full textAbstract:
Thesis (Ph. D.)--University of California, San Diego, 2007.Title from first page of PDF file (viewed Juen 21, 2007). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 70-71).