Student Number : 9804032J - PhD thesis - School of Mathematics - Faculty of Science / The focus of this thesis is the spectral structure of second order self-adjoint differential operators on graphs. Various function spaces on graphs are defined and we define, in terms of both differential systems and the afore noted function spaces, boundary value problems on graphs. A boundary value problem on a graph is shown to be spectrally equivalent to a system with separated boundary conditions. An example is provided to illustrate the fact that, for Sturm-Liouville operators on graphs, self-adjointness does not necessarily imply regularity. We also show that since the differential operators considered are self-adjoint the algebraic and geometric eigenvalue multiplicities are equal. Asymptotic bounds for the eigenvalues are found using matrix Pr¨ufer angle methods. Techniques common in the area of elliptic partial differential equations are used to give a variational formulation for boundary value problems on graphs. This enables us to formulate an analogue of Dirichlet-Neumann bracketing for boundary value problems on graphs as well as to establish a min-max principle. This eigenvalue bracketing gives rise to eigenvalue asymptotics and consequently eigenfunction asymptotics. Asymptotic approximations to the Green’s functions of Sturm-Liouville boundary value problems on graphs are obtained. These approximations are used to study the regularized trace of the differential operators associated with these boundary value problems. Inverse spectral problems for Sturm-Liouville boundary value problems on graphs resembling those considered in Halberg and Kramer, A generalization of the trace concept, Duke Math. J. 27 (1960), 607-617, for Sturm-Liouville problems, and Pielichowski, An inverse spectral problem for linear elliptic differential operators, Universitatis Iagellonicae Acta Mathematica XXVII (1988), 239-246, for elliptic boundary value problems, are solved. Boundary estimates for solutions of non-homogeneous boundary value problems on graphs are given. In particular, bounds for the norms of the boundary values of solutions to the non-homogeneous boundary value problem in terms of the norm of the non-homogeneity are obtained and the eigenparameter dependence of these bounds is studied. Inverse nodal problems on graphs are then considered. Eigenfunction and eigenvalue asymptotic approximations are used to provide an asymptotic expression for the spacing of nodal points on each edge of the graph from which the uniqueness of the potential, for given nodal data, is deduced. An explicit formula for the potential in terms of the nodal points and eigenvalues is given.

Magister Educationis - MEd / Algebraic graphs are a difficult topic for most secondary school mathematics learners. My experience as a Mathematics teacher in the Further Education and Training Phase (FET) is that learners solve problems involving graphs with difficulty. Consequently, the purpose of this research was to investigate learners’ ways of working with algebraic graphs in high-stakes examinations including their errors and misconceptions in this respect. The investigation carried out to identify learners’ errors and misconceptions is based on the analysis of 444 scripts from the 2012 grade 12 final Mathematics examination. More specifically, the study aimed to investigate the ways learners used to solve questions related to graphs in this examination. The focus of the study was the algebraic graphs tested in Paper 1 of the National Senior Certificate (NSC) examination with an emphasis on the identification of errors exhibited in the learners’ scripts. The study adopted a qualitative approach using documentary analysis methodology. As data, the study used the scripts of the final grade 12 Mathematics examinations of schools participating in a project for the improvement of Mathematics based at the University of the Western Cape (UWC). The analysis of learners’ scripts reveals that learners make many errors when they work with algebraic graphs. These errors that have been found in this investigation were coordinate, intercept, domain and range, asymptote, identification, drawing and function errors. Additional errors which were identified are transformation and inverse errors.

Neste projeto inicia-se o estudo de classificação de aplicações estáveis. Para isto usamos grafos que irão corresponder ao conjunto singular destas aplicações. Em um primeiro momento estudamos o caso de aplicações estáveis de superfícies no plano e depois estudamos aplicações estáveis de 3-variedades em \'R POT. 3\' / In this project we began the study of classification of stable maps. For this we use graphs that correspond to the singular set of these applications. At first we study the case of stable maps of surfaces in the plane and then we study stable maps of a 3-manifold in \'R POT. 3\'

In summary, the viewpoint of random graphs indeed provides us an opportunity of improving some existing machine learning algorithms. / In this thesis, we establish three machine learning models on random graphs: Heat Diffusion Models on Random Graphs, Predictive Random Graph Ranking, and Random Graph Dependency. The heat diffusion models on random graphs lead to Graph-based Heat Diffusion Classifiers (G-HDC) and a novel ranking algorithm on Web pages called DiffusionRank. For G-HDC, a random graph is constructed on data points. The generated random graph can be considered as the representation of the underlying geometry, and the heat diffusion model on them can be considered as the approximation to the way that heat flows on a geometric structure. Experiments show that G-HDC can achieve better performance in accuracy in some benchmark datasets. For DiffusionRank, theoretically we show that it is a generalization of PageRank when the heat diffusion coefficient tends to infinity, and empirically we show that it achieves the ability of anti-manipulation. / Predictive Random Graph Ranking (PRGR) incorporates DiffusionRank. PRGR aims to solve the problem that the incomplete information about the Web structure causes inaccurate results of various ranking algorithms. The Web structure is predicted as a random graph, on which ranking algorithms are expected to be improved in accuracy. Experimental results show that the PRGR framework can improve the accuracy of the ranking algorithms such as PageRank and Common Neighbor. / Three special forms of the novel Random Graph Dependency measure on two random graphs are investigated. The first special form can improve the speed of the C4.5 algorithm, and can achieve better results on attribute selection than gamma used in Rough Set Theory. The second special form of the general random graph dependency measure generalizes the conditional entropy because it becomes equivalent to the conditional entropy when the random graphs take their special form-equivalence relations. Experiments demonstrates that the second form is an informative measure, showing its success in decision trees on small sample size problems. The third special form can help to search two parameters in G-HDC faster than the cross-validation method. / Yang, haixuan. / "August 2007." / Advisers: Irwin King; Michael R. Lyu. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1125. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 184-197). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

A Tutte trail T of a graph G is a trail such that every component of GnV (T) has at most three edges connecting it to T. In 1992, Bill Jackson conjectured that every 2-edge-connected graph G has a Tutte closed trail. In this thesis, we show that Jackson's conjecture is true when G is embedded on the plane and the projective plane. We also give some partial results when G is embedded on the torus.

Alon 和Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) 證明了如果一個圖是ε -非二部圖，那麼階數為Ỡ(1/ε) 的隨機導出于圖以很大概率是非二部圖。我們進一步猜想，這個導出子圖以很大概率是Ω(ε)-非二部圖。Gonen 和Ron (RANDOM 2007) 證明了當圖的最大度不超過O (εn )時猜想成立。我們將對更一般的情形給出證明，對於任意d，所有d 正則(或幾乎d 正則)的圖猜想成立。 / 假設猜想成立的情況下，我們證明二分屬性是可以被單側誤差在O(1/ε^c ) 時間內檢驗的，其中c 是一個嚴格小於2 的常數，而這個結果也改進了Alon 和Krivelevich 的檢驗算法。由於己知對二分屬性的非適應性的檢驗算法需要Ω(1 /ε²) 的複雜性(Bogdanov 和Trevisan ， CCC 2004) ，我們的結果也得出，假設猜想成立，適應性對檢驗二分屬性是有幫助的。 / 另外一個有很多屬性檢驗問題被廣泛研究的領域是布爾函數。對布爾函數單調性的檢驗也是屬性檢驗的經典問題。給定對布爾函數f: {0,1}{U+207F} → {0,1} 的訪問，在[18]中，證明了檢驗算法複雜性的下界是Ω(√n) 。另一方面，在[21]中，作者們構造了一個複雜性為O(n) 的算法。在本文中，我們刻畫一些單調布爾函數的本質，設計算法并分析其對於一些困難例子的效果。最近，在[14] 中， 一個類似的算法被證明是非適應性，單側誤差，複雜性為Ỡ (n⁵/⁶ ε⁻⁵/³) 的算法。 / Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of Ỡ (1/ε) vertices is not bipartite with high probability. We conjecture that the induced subgraph is Ω(ε)-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. / Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1=ε{U+1D9C}), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require Ω(1/ε²) queries (Bogdanov and Trevisan, CCC2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness. / The other area in which various properties have been well studied is boolean function. Testing monotonicity of Boolean functions is a classical question in property testing. Given oracle access to a Boolean function f : {0, 1}{U+207F} →{0, 1}, in [18], it is shown a lower bound of testing is Ω(√n). On the other hand, in [21], the authors introduced an algorithm to test monotonicity using O(n) queries. In this paper, we characterize some nature of monotone functions, design a tester and analyze the performance on some generalizations of the hard case. Recently, in [14], a similar tester is shown to be a non-adaptive, one-sided error tester making Ỡ (n⁵/⁶ ε⁻⁵/³) queries. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Fan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 76-79). / Abstracts also in Chinese. / Abstract --- p.i / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Property Testing --- p.1 / Chapter 1.2 --- Testing Bipartiteness --- p.4 / Chapter 1.3 --- Testing Monotonicity --- p.7 / Chapter 2 --- Testing Bipartiteness --- p.11 / Chapter 2.1 --- Background --- p.11 / Chapter 2.1.1 --- Our result --- p.11 / Chapter 2.1.2 --- The algorithms of Gonen and Ron --- p.13 / Chapter 2.1.3 --- Our proof --- p.16 / Chapter 2.1.4 --- Notation --- p.19 / Chapter 2.2 --- Splitting the vertices by degree --- p.19 / Chapter 2.3 --- The algorithm for high degree vertices --- p.20 / Chapter 2.4 --- Eliminating the high degree vertices --- p.22 / Chapter 2.5 --- From an XOR game to a bipartite graph --- p.33 / Chapter 2.6 --- Proof of the main theorem --- p.35 / Chapter 2.7 --- Proof of the conjecture for regular graphs --- p.37 / Chapter 3 --- Testing Monotonicity --- p.40 / Chapter 3.1 --- Towards an improved tester --- p.40 / Chapter 3.1.1 --- Properties of Distribution D --- p.42 / Chapter 3.1.2 --- An Alternative Representation of D --- p.46 / Chapter 3.1.3 --- Performance of D on Decreasing Functions --- p.51 / Chapter 3.1.4 --- Functions Containing Ω(2{U+207F}) Disjoint Violating Edges --- p.54 / Chapter 3.2 --- A o(n) Monotonicity Tester [14] and Some Improvements --- p.62 / Chapter 3.2.1 --- A o(n) Monotonicity Tester [14] --- p.62 / Chapter 3.2.2 --- An Alternative Proof of Theorem 3.2.2 --- p.65 / Chapter 4 --- Other Related Results --- p.67 / Chapter 4.1 --- Short Odd Cycles in Graphs that are Far From Bipartiteness --- p.67 / Chapter 4.2 --- Fourier Analysis on Boolean Functions --- p.69 / Bibliography --- p.76

L’électrolyse est une technologie qui permet de répondre à deux problématiques cruciales. D’une part, répondre au besoin en stockage d’énergie liée à l’intégration de sources intermittentes sur les réseaux électriques. D’autre part, répondre à la croissance de la demande en hydrogène, liée aux marchés naissants de l’hydrogène énergie. La nature des besoins liés au développement de la technologie d’électrolyse implique des sollicitations intermittentes dont les impacts quant au fonctionnement du système sont encore méconnus. En ce sens, et face aux manques de la littérature quant à la modélisation à l’échelle système de la technologie d’électrolyse PEM, un nouveau modèle est développé. Pour cela, le formalisme de modélisation graphique Bond Graph est utilisé, notamment pour sa capacité à représenter tout type d’échange énergétique de manière unifiée. Le modèle développé permet de représenter l’intégralité d’un système d’électrolyse PEM, ses différents composants et lois de contrôle associées. Il est validé sur la base du comportement dynamique d’une installation semi-industrielle disponible au CEA. Ce modèle est ensuite utilisé pour identifier et comprendre les enjeux liées à une sollicitation intermittente d’un système d’électrolyse PEM d’un point de vue de l’efficacité du système, de sa flexibilité et de sa capacité de suivi de charge, de sa fiabilité, de sa sûreté ou encore de sa durabilité. Différentes modifications de conception sont simulées et évaluées à la lumière de ces différents enjeux. Finalement, le modèle Bond Graph est exploité d’un point de vue de ses propriétés structurelles afin d’analyser les conditions de surveillabilité d’un système d’électrolyse PEM. / PEM Electrolysis is a technology which to enable to face two major challenges : (i) Fulfill the need of energy storage caused by the integration of intermittent energy sources on electricity networks; (ii) Cope with the growing need of carbon free hydrogen caused by the future market applications of hydrogen energy. These particular needs, regarding electrolysis technology development, involve an intermittent operating mode which impacts on the dynamic behavior of the system remain unknown. Modelling is a critical tool to understand these issues and provide a thorough analysis. State of the art of existing modelling works highlighted that only a few models take into account the dynamic of the whole system including Balance of Plant. Therefore a new dynamic and multiphysic model was developed under Bond Graph formalism. This graphical modelling formalism was selected especially thanks to its ability to represent any kind of power exchange in a unified way. The model enables to represent the whole system including balance of plant and associated control laws. It is validated on the dynamic behavior of an experimental device available in CEA. The model is then used in order to identify and understand the issues related to intermittent operation of a PEM electrolysis system. These issues are related to system efficiency, flexibility, reliability, safety and durability. Regarding these issues, some design changes are simulated and assessed. Finally, the Bond Graph model and its structural properties enable to perform diagnosis and monitorability analyses of a PEM electrolysis system.

In this thesis, we provide an algorithm for constructing strongly eutactic lattices from vertex transitive graphs. We show that such construction produces infinitely many strongly eutactic lattices in arbitrarily large dimensions. We demonstrate our algorithm on the example of the famous Petersen graph using Maple computer algebra system. We also discuss some additional examples of strongly eutactic lattices obtained from notable vertex transitive graphs. Further, we study the properties of the lattices generated by product graphs, complement graphs, and line graphs of vertex transitive graphs. This thesis is based on the research paper written by the author jointly with L. Fukshansky, D. Needell and J. Park.

Shortest path problems arise in a variety of applications ranging from transportation planning to network routing among others. One group of these problems involves finding shortest paths in graphs where the edge weights are defined by probability distributions. While some research has addressed the problem of finding a single shortest path, no research has been done on finding multiple paths in such graphs. This thesis addresses the problem of finding paths for multiple robots through a graph in which the edge weights represent the probability that each edge will fail. The objective is to find paths for n robots that maximize the probability that at least k of them will arrive at the destination. If we make certain restrictions on the edge weights and topology of the graph, this problem can be solved in O(n log n)time. If we restrict only the topology, we can find approximate solutions which are still guaranteed to be better than the single most reliable path.

We consider Benjamini-Schramm limits of Rauzy Graphs of low-complexity words. Low-complexity words are infinite words (over a finite alphabet), for which the number of subwords of length n is bounded by some Kn --- examples of such a word include the Thue-Morse word 01101001... and the Fibonacci word. Rauzy graphs Rn (omega) have the length n subwords of omega as vertices, and the oriented edges between vertices indicate that two words appear immediately adjacent to each other in omega (with overlap); the edges are also equipped with labels, which indicate what "new letter" was appended to the end of the terminal vertex of an edge. In a natural way, the labels of consecutive edges in a Rauzy graph encode subwords of omega. The Benjamini-Schramm limit of a sequence of graphs is a distribution on (possibly infinite) rooted graphs governed by the convergence in distribution of random neighborhoods of the sequence of finite graphs. In the case of Rauzy graphs without edge-labelings, we establish that the Rauzy graphs of aperiodic low-complexity words converge to the line graph in the Benjamini-Schramm sense. In the same case, but for edge-labelled Rauzy graphs, we also prove that that the limit exists when the frequencies of all subwords in the infinite word, omega, are well defined (when the subshift of omega is uniquely ergodic), and we show that the limit can be identified with the unique ergodic measure associated to the subshift generated by the word. The eventually periodic (i.e. finite) cases are also shown. Finally, we show that for non-uniquely ergodic systems, the Benjamini-Schramm limit need not exist ---though it can in some instances--- and we provide examples to demonstrate the variety of possible behaviors.