1 |
Random StructuresBall, Neville January 2015 (has links)
For many combinatorial objects we can associate a natural probability distribution on the members of the class, and we can then call the resulting class a class of random structures. Random structures form good models of many real world problems, in particular real networks and disordered media. For many such problems, the systems under consideration can be very large, and we often care about whether a property holds most of the time. In particular, for a given class of random structures, we say that a property holds with high probability if the probability that that property holds tends to one as the size of the structures increase. We examine several classes of random structures with real world applications, and look at some properties of each that hold with high probability. First we look at percolation in 3 dimensional lattices, giving a method for producing rigorous confidence intervals on the percolation threshold. Next we look at random geometric graphs, first examining the connectivity thresholds of nearest neighbour models, giving good bounds on the threshold for a new variation on these models useful for modelling wireless networks, and then look at the cop number of the Gilbert model. Finally we look at the structure of random sum-free sets, in particular examining what the possible densities of such sets are, what substructures they can contain, and what superstructures they belong to.
|
2 |
Threshold Phenomena in Random Constraint Satisfaction ProblemsConnamacher, Harold 30 July 2008 (has links)
Despite much work over the previous decade, the Satisfiability Threshold
Conjecture remains open. Random k-SAT, for constant k >= 3,
is just one family of a large number
of constraint satisfaction problems that are conjectured to have exact
satisfiability thresholds, but for which the existence and location of these
thresholds has yet to be proven.
Of those problems for which we are able to prove
an exact satisfiability threshold, each seems to be fundamentally different
than random 3-SAT.
This thesis defines a new family of
constraint satisfaction problems with constant size
constraints and domains and which
contains problems that are NP-complete and a.s.\ have exponential
resolution complexity. All four of these properties hold for k-SAT, k >= 3,
and the
exact satisfiability threshold is not known for any constraint
satisfaction problem
that has all of these properties. For each problem in the
family defined in this
thesis, we determine
a value c such that c is an exact satisfiability threshold if a certain
multi-variable function has a unique maximum at a given point
in a bounded domain. We
also give numerical evidence that this latter condition holds.
In addition to studying the satisfiability threshold, this thesis
finds exact
thresholds for the efficient behavior of DPLL using the unit clause heuristic
and a variation of the generalized unit clause heuristic,
and this thesis proves an analog
of a conjecture on the satisfiability of (2+p)-SAT.
Besides having similar properties as k-SAT, this new family of
constraint satisfaction problems
is interesting to study in its own right because it generalizes the
XOR-SAT problem and it has close ties
to quasigroups.
|
3 |
Threshold Phenomena in Random Constraint Satisfaction ProblemsConnamacher, Harold 30 July 2008 (has links)
Despite much work over the previous decade, the Satisfiability Threshold
Conjecture remains open. Random k-SAT, for constant k >= 3,
is just one family of a large number
of constraint satisfaction problems that are conjectured to have exact
satisfiability thresholds, but for which the existence and location of these
thresholds has yet to be proven.
Of those problems for which we are able to prove
an exact satisfiability threshold, each seems to be fundamentally different
than random 3-SAT.
This thesis defines a new family of
constraint satisfaction problems with constant size
constraints and domains and which
contains problems that are NP-complete and a.s.\ have exponential
resolution complexity. All four of these properties hold for k-SAT, k >= 3,
and the
exact satisfiability threshold is not known for any constraint
satisfaction problem
that has all of these properties. For each problem in the
family defined in this
thesis, we determine
a value c such that c is an exact satisfiability threshold if a certain
multi-variable function has a unique maximum at a given point
in a bounded domain. We
also give numerical evidence that this latter condition holds.
In addition to studying the satisfiability threshold, this thesis
finds exact
thresholds for the efficient behavior of DPLL using the unit clause heuristic
and a variation of the generalized unit clause heuristic,
and this thesis proves an analog
of a conjecture on the satisfiability of (2+p)-SAT.
Besides having similar properties as k-SAT, this new family of
constraint satisfaction problems
is interesting to study in its own right because it generalizes the
XOR-SAT problem and it has close ties
to quasigroups.
|
4 |
Phase transitions in the evolution of partially ordered setsTaraz, Anuschirawan Ralf 06 January 1999 (has links)
Unter dem Evolutionsprozeß eines Objekts, das aus einer gegebenen Klasse zufällig ausgewählt wird, versteht man das folgende Gedankenexperiment. Zu einem geeigneten Parameter der Objekte der Klasse betrachtet man die Teilklasse derjenigen Objekte, bei denen dieser Parameter einen bestimmten Wert x annimmt. Dadurch stellen sich die folgenden Fragen: Wie sieht ein typisches Objekt dieser Teilklasse aus? Wieviele Objekte gibt es in der Teilklasse? Und: Wie verändern sich die Antworten auf die ersten beiden Fragen, wenn sich x verändert? Die vorliegende Dissertation behandelt Phasenübergänge im Evolutionsprozeß teilweiser Ordnungen und bestimmt die Anzahl teilweiser Ordnungen mit einer gegebenen Anzahl vergleichbarer Paare. Wir bezeichnen durch Pn,d die Klasse aller teilweisen Ordnungen mit n Punkten und dn2 vergleichbaren Paaren. 1978 bestimmte Dhar |Pn,d| im Intervall 1/8 < d < 3/16 und zeigte, daß hier eine typische Ordnung aus drei "Ebenen" besteht. 1979 bestimmten Kleitman und Rothschild |Pn,d| im Intervall 0 < d < 1/8 und zeigten, daß hier eine typische Ordnung aus zwei Ebenen besteht, also bipartit ist. Das Hauptergebnis der Dissertation ist es, ein vollständiges Bild des Evolutionsprozesses zu geben. Wir bestimmen |Pn,d| im gesamten Intervall 0 < d < 1/2 und zeigen, daß es unendlich viele Phasenübergänge gibt. Abschließend beschreiben wir, wie sich die Struktur einer typischen Ordnung während dieser Phasen verändert. / The evolution process of a random structure from a certain class denotes the following "experiment". Choose a parameter of the objects in the class under consideration and consider only the subclass of those objects where the parameter is equal to a fixed value x. Then the following questions arise quite naturally: What does a typical object from this subclass look like? How many objects are there in this subclass? And how do the answers to the first two questions change when x changes? This thesis investigates the phase transitions in the evolution of partially ordered sets and determines the number of partially ordered sets with a given number of comparable pairs. Denote by Pn,d the class of all n-point posets with dn2 comparable pairs. In 1978, Dhar determined |Pn,d| in the range 1/8 < d < 3/16 and showed that here a typical poset consists of three layers. In 1979, Kleitman and Rothschild determined |Pn,d| in the range 0 < d < 1/8 and showed that here a typical poset consists of two layers, i.e. it is bipartite. The main result of this thesis is to complete the picture by describing the whole evolution process of Pn,d in the range 0 < d < 1/2. We determine |Pn,d| for any d and show that there exist an infinite number of phase transitions. Finally we describe how the structure of a typical partially ordered set changes during these phases.
|
Page generated in 0.0946 seconds