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 4 of 4 for “"ramanujan graph"”.
-
Bounds on k-Regular Ramanujan Graphs and Separator Theorems
Expander graphs are a family of graphs that are highly connected. Finding explicit examples of expander graphs which are also sparse is a difficult problem. The best type of expander graph in a. certain sense is a Ramanujan graph. Families of graphs that have separator theorems fail to be Ramanujan …
-
Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts
… the Unique Games Conjecture when the constraint graph is restricted to the Boolean Hypercube. The Boolean Hypercube is a well studied graph family on which existing spectral methods fail to achieve a sub exponential time bound. We initiate the study of the behaviour of the standard semi-definite …
-
The Expanding Constant, Ramanujan Graphs, and Winnie Li Graphs
The expanding constant is a measure of graph connectivity that is important for certain applications. This paper discusses the mathematical foundations for the construction of Winnie Li's graphs and for the proof that Winnie Li's graphs are Ramanujan. The paper also establishes the implications of …
-
Combinatorial aspects of synchronisation, percolation, and arithmetic
… with interactions given by the edges of a graph. We show that a graph with sufficient expansion must be globally synchronising, meaning that the Kuramoto model on such a graph will converge to the fully synchronised state, namely the one where all the oscillators have the same phase, for …