Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"Hypergraph coloring"”.
-
On Some Hypergraph Coloring Algorithms
… containing no copies of the Fano plane as a subhypergraph. Since the Fano plane is not bipartite, it holds that B_n ⊆ F_n, which Person and Schacht proved is nearly an equality (in a sense made precise later). They also established an algorithm which properly and minimally colors a given H ∈ F_n …
-
Phylogenetic decisiveness and no-rainbow hypergraph coloring
… Here we relate the decisiveness problem to a hypergraph coloring problem. We use this connection to (1) show that the decisiveness problem is co-NP complete, (2) obtain lower bounds on the amount of coverage needed to achieve decisiveness, (3) devise an exact algorithm for decisiveness, (4) …
-
Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems
… packing type problems: (i) a particular kind of hypergraph coloring problem, and (ii) vector packing problem. The hypergraph coloring problem is connected to the resource constrained scheduling problem and vector packing is a particular multi-dimensional generalization of the well known bin …
-
An Overview of the Constructive Local Lemma
… provide an implementation of the algorithm to a hypergraph coloring problem.
-
Intersperse Coloring
In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter …
-
A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms
… with the motivation rooted in Ramsey theory, hypergraph coloring problems, and others, we explore how the Lovász Local Lemma transformed probabilistic existence proofs in Combinatorics and explore its applications. We also examine some generalizations of the lemma, including the algorithmic …
-
Algorithms and Generalizations for the Lovasz Local Lemma
… This leads to improved bounds for k-SAT and hypergraph coloring among other applications. We describe an extension of the Moser-Tardos algorithm based on partial resampling, and use this to obtain better bounds for problems involving sums of independent random variables, such as column-sparse …
-
Derandomizing Concentration Inequalities with dependencies and their combinatorial applications
… In Chapter 8, we analyze the constrained hypergraph coloring problem given in Ahuja and Srivastav (2002), which generalizes both the property B problem for the non-monochromatic 2-coloring of hypergraphs and the multidimensional bin packing problem using the bounded differences inequality …
-
Formal group laws and hypergraph colorings
… group laws and chromatic symmetric functions of hypergraphs, two seemingly unrelated topics in the theory of symmetric functions. A formal group law is a symmetric function of the form $f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots)$ for a formal power series $f(x) \in \mathbb{Q}[[x]]$. A …
-
Coloring and constructing (hyper)graphs with restrictions
… questions regarding the existence of graphs and hypergraphs with certain coloring properties and other structural properties. In Chapter 2 we consider color-critical graphs that are nearly bipartite and have few edges. We prove a conjecture of Chen, Erdős, Gyárfás, and Schelp concerning the …