Algebraic methods for chromatic polynomial

مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی

منو

" Algebraic methods for chromatic polynomial "
Georgiou, Nicholas

Document Type	:	Latin Dissertation
Record Number	:	1098472
Doc. No	:	TLets543144
Main Entry	:	Georgiou, Nicholas
Title & Author	:	Algebraic methods for chromatic polynomial\ Georgiou, Nicholas
College	:	London School of Economics and Political Science (LSE)
Date	:	2003
student score	:	2003
Degree	:	Ph.D.
Abstract	:	This thesis is presented in two parts. In the first part, we study a family of models of random partial orders, called classical sequential growth models, introduced by Rideout and Sorkin as possible models of discrete space-time. We analyse a particular model, called a random binary growth model, and show that the random partial order produced by this model almost surely has infinite dimension. We also give estimates on the size of the largest vertex incomparable to a particular element of the partial order. We show that there is some positive probability that the random partial order does not contain a particular subposet. This contrasts with other existing models of partial orders. We also study "continuum limits" of sequences of classical sequential growth models. We prove results on the structure of these limits when they exist, highlighting a deficiency of these models as models of space-time. In the second part of the thesis, we prove some correlation inequalities for mappings of rooted trees into complete trees. For T a rooted tree we can define the proportion of the total number of embeddings of T into a complete binary tree that map the root of T to the root of the complete binary tree. A theorem of Kubicki, Lehel and Morayne states that, for two binary trees with one a subposet of the other, this proportion is larger for the larger tree. They conjecture that the same is true for two arbitrary trees with one a subposet of the other. We disprove this conjecture by analysing the asymptotics of this proportion for large complete binary trees. We show that the theorem of Kubicki, Lehel and Morayne can be thought of as a correlation inequality which enables us to generalise their result in other directions.
Subject	:	QA Mathematics
Added Entry	:	London School of Economics and Political Science (LSE)