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 15 of 15 for “"Graphs, hypergraphs"”.
-
Hilbert Series of Graphs, Hypergraphs, and Monomial Ideals
In this dissertation, identities for Hilbert series of quotients of polynomial rings by monomial ideals are explored, beginning in the contexts of graph and hypergraph rings and later generalizing to general monomial ideals. These identities are modeled after constructive identities from graph …
-
Symmetries
Automorphisms of graphs, hypergraphs and disgraphs are investigated. The invariance of the chromatic polynomial in the rotor effect is disproved. New invariance results are obtained. It is shown that given any integer k > 2 , almost every finite group acts as the regular full automorphism group of …
-
Some Take-Away Games on Discrete Structures
… structures, including but not limited to graphs, hypergraphs, polygonal complexes, and partially ordered sets. While a universal winning strategy has yet to be found, results have been found in certain cases. In 2003 R. Riehemann focused on Subset Take-Away on bipartite graphs and produced …
-
The complexity of expansion problems
… notions of expansion, namely edge expansion in graphs, vertex expansion in graphs and hypergraph expansion. We define suitable notions of spectra w.r.t. these notions of expansion. We show how the notion Cheeger's Inequality goes across these three problems. We study higher order variants of …
-
Learning from Partially Labeled Data: Unsupervised and Semi-supervised Learning on Graphs and Learning with Distribution Shifting
… algorithms, currently based on undirected graphs, to more general graph types, including directed graphs, hypergraphs and complex networks. These richer graph representations allow one to more naturally capture the intrinsic data relationships that exist, for example, in Web data, …
-
Low-depth circuit size bounds using combinatorial methods
… computing the $k$-clique function on $n$ vertex graphs requires the AND of at least $2^{n/4k}$ monotone, constant-depth, and polynomial-sized circuits, for sufficiently large values of $k$. <br><br>Then, depth 3 circuits computing the threshold function will be studied. A connection is proved …
-
Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra
… probabilistic combinatorics, Ricci curvature of graphs, spectral hypergraph theory and the interplay between these areas. The first main focus of this thesis is to investigate several Ramsey-type problems on graphs, hypergraphs and sequences using probabilistic, combinatorial, algorithmic and …
-
Turing machine algorithms and studies in quasi-randomness
… we study some aspects of quasi-randomness in graphs. Specifically, we provide an algorithm and a lower bound for two different kinds of regularity lemmas. Our algorithm for FK-regularity is derived using a spectral characterization of quasi-randomness. We also use a similar spectral connection …
-
Analytic properties of sparse graphs and hypergraphs
… variables. Next, we define a class of weighted hypergraphs that satisfy relative counting and removal lemmas. Finally, we present number theoretical and algorithmic applications of the aforementioned results.
-
Some Combinatorial Games on Hypergraphs
… problems and presents three games played on hypergraphs. In Chapter 2, we present theoretical results related to the existence of paths and expanders in hypergraphs. Chapters 3 and 4 discuss properties of random graph processes and an approximation of the number of edges in a k-nearest …
-
Conceptualização de bases de dados orientadas a grafos usando dígrafos
A crescente complexidade dos sistemas de informação contemporâneos, impulsionada pela interligação progressiva de dados, processos e intervenientes em múltiplas escalas, tem evidenciado limitações significativas nas abordagens tradicionais de modelação de dados. Os modelos relacionais clássicos e …
-
Graphical structure of unsatisfiable boolean formulae
… of a novel graph decision problem called GraphSAT. Using the tools of topology and graph theory, this new variant builds upon the classical logic and computer science problem of boolean satisfiability k-SAT. k-SAT asks if there exists a truth assignment that satisfies a given boolean …
-
List colouring hypergraphs and extremal results for acyclic graphs
We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, …
-
Sampling uniform hypergraphs with given degrees
Graphs are combinatorial objects commonly used to model relationships between pairs of entities. Hypergraphs are a generalization of graphs in which edges connect an arbitrary number of vertices. We consider hypergraphs in which each edge has size k, each vertex has a degree specified by a degree …
-
Coloring problems in combinatorics and descriptive set theory
… new bounds on measurable chromatic numbers of graphs induced by group actions. In Chapter 4, we study shift actions of countable groups on spaces of the form A, where A is a finite set, and apply the Lovász Local Lemma to find “large” closed shift-invariant subsets X A on which the induced …