This is an expository thesis. In this thesis we study out-orientations of hypergraphs, where every hyperarc has one tail vertex. We study hypergraphs that admit out-orientations covering supermodular-type connectivity requirements. For this, we follow a paper of Frank. We also study the Steiner rooted orientation problem. Given a hypergraph and a subset of vertices S ⊆ V, the goal is to give necessary and sufficient conditions for an orientation such that the connectivity between a root vertex and each vertex of S is at least k, for a positive integer k. We follow a paper by Kiraly and Lau, where they prove that every 2k-hyperedge connected hypergraph has such an orientation.

Thesis (M.S.)--West Virginia University, 2000. / Title from document title page. Document formatted into pages; contains iii, 34 p. Includes abstract. Includes bibliographical references (p. 33-34).

Call number: LD2668 .T4 1985 G63 / Master of Science

No description available.

Chan, Yuk Hei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 49-51). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Definition --- p.1 / Chapter 1.1.1 --- Hypergraph Matching --- p.1 / Chapter 1.1.2 --- k-Set Packing --- p.2 / Chapter 1.1.3 --- k-Dimensional Matching --- p.2 / Chapter 1.1.4 --- Related Problems --- p.2 / Chapter 1.2 --- Main Result --- p.5 / Chapter 1.3 --- Overview of the Thesis --- p.6 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Matching --- p.8 / Chapter 2.1.1 --- Augmenting Path --- p.8 / Chapter 2.1.2 --- Linear Programming --- p.10 / Chapter 2.1.3 --- Matching in General Graphs --- p.11 / Chapter 2.1.4 --- Approximate Min-max Relation for Hypergraphs --- p.11 / Chapter 2.2 --- Local Search --- p.12 / Chapter 2.2.1 --- Unweighted k-Set Packing --- p.12 / Chapter 2.2.2 --- Weighted k-Set Packing ´ؤ (k- - 1 + ₂ё)-approximation --- p.14 / Chapter 2.2.3 --- Weighted k-Set Packing´ؤ(2(k + l)/3 + ₂ё)-approximation --- p.15 / Chapter 2.2.4 --- Weighted k-Set Packing´ؤ((k + l)/2 + ₂ё)-approximation --- p.16 / Chapter 2.3 --- Iterative Rounding --- p.17 / Chapter 2.3.1 --- Basic Solution --- p.17 / Chapter 2.3.2 --- Bipartite Matching --- p.19 / Chapter 2.3.3 --- Generalized Steiner Network Problem --- p.20 / Chapter 2.3.4 --- Minimum Bounded Degree Spanning Tree --- p.22 / Chapter 2.4 --- Packing Problems --- p.24 / Chapter 2.4.1 --- Projective Plane --- p.26 / Chapter 2.5 --- Local Ratio --- p.28 / Chapter 2.5.1 --- Vertex Cover --- p.28 / Chapter 2.5.2 --- Local Ratio Theorem --- p.29 / Chapter 2.5.3 --- Feedback Vertex Set in Tournaments --- p.29 / Chapter 2.5.4 --- Fractional Local Ratio --- p.31 / Chapter 2.5.5 --- Maximum Weight Independent Set in t-interval Graph --- p.31 / Chapter 3 --- k-Dimensional Matching --- p.33 / Chapter 3.1 --- Integrality Gap of the Standard LP Relaxation --- p.33 / Chapter 3.1.1 --- Approximation Algorithm for Unweighted k-D Matching --- p.34 / Chapter 3.1.2 --- Fractional Colouring --- p.35 / Chapter 3.1.3 --- Produce an Ordering --- p.37 / Chapter 3.2 --- Approximation Algorithm for Weighted k-D Matching --- p.38 / Chapter 4 --- k-Set Packing --- p.40 / Chapter 4.1 --- Integrality Gap of the Standard LP Relaxation --- p.40 / Chapter 4.2 --- Improved LP Relaxation for 3-SP --- p.41 / Concluding Remarks --- p.48 / Bibliography --- p.49

Thesis (M.S.)--Rochester Institute of Technology, 1989. / References: leaves 34-37.

Thesis (M.S.)--University of Nevada, Reno, 2008. / "May, 2008." Includes bibliographical references (leaves 115-118). Online version available on the World Wide Web.

The problem we study in this thesis asks under which conditions an r-factorization of Kₘʰ can be embedded into an s-factorization of Kₙʰ. This problem is a generalization of a problem posed by Peter Cameron which asks under which conditions a 1-factorization of Kₘʰ can be embedded into a 1-factorization of Kₙʰ. This was solved by Häggkvist and Hellgren. We study sufficient conditions in the case where s = h and m divides n. To that end, we take inspiration from a paper by Amin Bahmanian and Mike Newman and simplify the problem to the construction of an "acceptable" partition. We introduce the notion of irreducible sums and link them to the main obstacles in constructing acceptable partitions before providing different methods for circumventing these obstacles. Finally, we discuss a series of open problems related to this case.

This thesis examines biomedical text mining with an application in bone biology. A special thanks is extended to Anita Park and Mark Jaeger from the Purdue University Graduate School Office, who acted as invaluable assets in the formatting of the thesis. IUPUI and every other university would be fortunate to have staff that respond in such a timely, corteous, and professional manner. / Indiana University-Purdue University Indianapolis (IUPUI) / The biological literature is a huge and constantly increasing source of information which the biologist may consult for information about their field, but the vast amount of data can sometimes become overwhelming. Medline, which makes a great amount of biological journal data available online, makes the development of automated text mining systems and hence “data-driven discovery” possible. This thesis examines current work in the field of text mining and biological literature, and then aims to mine documents pertaining to bone biology. The documents are retrieved from PubMed, and then direct associations between the terms are computers. Potentially novel transitive associations among biological objects are then discovered using the transitive closure algorithm and the maximum flow algorithm. The thesis discusses in detail the extraction of biological objects from the collected documents and the co-occurrence based text mining algorithm, the transitive closure algorithm, and the maximum network flow which were then run to extract the potentially novel biological associations. Generated hypotheses (novel associations) were assigned with significance scores for further validation by a bone biologist expert. Extension of the work in to hypergraphs for enhanced meaning and accuracy is also examined in the thesis.

Dois problemas combinatórios são estudados: (i) determinar a quantidade de cópias de um hipergrafo fixo em um hipergrafo uniforme pseudoaleatório, e (ii) estimar números de Ramsey de ordem dois e três para grafos com largura de banda pequena e grau máximo limitado. Apresentamos um lema de contagem para estimar a quantidade de cópias de um hipergrafo k-uniforme linear livre de conectores (conector é uma generalização de triângulo, para hipergrafos) que estão presentes em um hipergrafo esparso pseudoaleatório G. Considere um hipergrafo k-uniforme linear H que é livre de conectores e um hipergrafo k-uniforme G com n vértices. Seja d_H=\\max\\{\\delta(J): J\\subset H\\} e D_H=\\min\\{k d_H,\\Delta(H)\\}. Estabelecemos que, se os vértices de G não possuem grau grande, famílias pequenas de conjuntos de k-1 elementos de V(G) não possuem vizinhança comum grande, e a maioria dos pares de conjuntos em {V(G)\\choose k-1} possuem a quantidade ``correta\'\' de vizinhos, então a quantidade de imersões de H em G é (1+o(1))n^{|V(H)|}p^{|E(H)|}, desde que p\\gg n^{1/D_H} e |E(G)|={n\\choose k}p. Isso generaliza um resultado de Kohayakawa, Rödl e Sissokho [Embedding graphs with bounded degree in sparse pseudo\\-random graphs, Israel J. Math. 139 (2004), 93--137], que provaram que, para p dado como acima, esse lema de imersão vale para grafos, onde H é um grafo livre de triângulos. Determinamos assintoticamente os números de Ramsey de ordem dois e três para grafos bipartidos com largura de banda pequena e grau máximo limitado. Mais especificamente, determinamos assintoticamente o número de Ramsey de ordem dois para grafos bipartidos com largura de banda pequena e grau máximo limitado, e o número de Ramsey de ordem três para tais grafos, com a suposição adicional de que ambas as classes do grafo bipartido têm aproximadamente o mesmo tamanho. / Two combinatorial problems are studied: (i) determining the number of copies of a fixed hipergraph in uniform pseudorandom hypergraphs, and (ii) estimating the two and three color Ramsey numbers for graphs with small bandwidth and bounded maximum degree. We give a counting lemma for the number of copies of linear k-uniform \\emph hypergraphs (connector is a generalization of triangle for hypergraphs) that are contained in some sparse hypergraphs G. Let H be a linear k-uniform connector-free hypergraph and let G be a k-uniform hypergraph with n vertices. Set d_H=\\max\\{\\delta(J)\\colon J\\subset H\\} and D_H=\\min\\{kd_H,\\Delta(H)\\}. We proved that if the vertices of G do not have large degree, small families of (k-1)-element sets of V(G) do not have large common neighbourhood and most of the pairs of sets in {V(G)\\choose k-1} have the `right\' number of common neighbours, then the number of embeddings of H in G is (1+o(1))n^p^, given that p\\gg n^ and |E(G)|=p. This generalizes a result by Kohayakawa, R\\\"odl and Sissokho [Embedding graphs with bounded degree in sparse pseudo\\-random graphs, Israel J. Math. 139 (2004), 93--137], who proved that, for p as above, this result holds for graphs, where H is a triangle-free graph. We determine asymptotically the two and three Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that both classes of the bipartite graph have almost the same size.