Dissertations / Theses on the topic 'Differential Graph'

Empty answers are a major problem by processing pattern matching queries in graph databases. Especially, there can be multiple reasons why a query failed. To support users in such situations, differential queries can be used that deliver missing parts of a graph query. Multiple heuristics are proposed for differential queries, which reduce the search space. Although they are successful in increasing the performance, they can discard query subgraphs relevant to a user. To address this issue, the authors extend the concept of differential queries and introduce top-k differential queries that calculate the ranking based on users’ preferences and significantly support the users’ understanding of query database management systems. A user assigns relevance weights to elements of a graph query that steer the search and are used for the ranking. In this paper the authors propose different strategies for selection of relevance weights and their propagation. As a result, the search is modelled along the most relevant paths. The authors evaluate their solution and both strategies on the DBpedia data graph.

Often we are confronted with heterogeneous multivariate data, i.e., data coming from several categories, and the interest may center on the differential structure of stochastic dependence among the variables between the groups. The focus in this work is on the two groups problem and is faced modeling the system through a Gaussian directed acyclic graph (DAG) couple linked in a fashion to obtain a joint estimation in order to exploit, whenever they exist, similarities between the graphs. The model can be viewed as a set of separate regressions and the proposal consists in assigning a non-local prior to the regression coefficients with the objective of enforcing stronger sparsity constraints on model selection. The model selection is based on Moment Fractional Bayes Factor, and is performed through a stochastic search algorithm over the space of DAG models.

Thesis (M.S.)--East Tennessee State University, 2004.
Title from electronic submission form. ETSU ETD database URN: etd-0322104-155516. Includes bibliographical references. Also available via Internet at the UMI web site.

The user data in social media platforms is an excellent source of information that is beneficial for both commercial and scientific purposes. However, recent times has seen that the user data is not always used for good, which has led to higher demands on user privacy. With accurate statistical research data being just as important as the privacy of the user data, the relevance of differential privacy has increased. Differential privacy allows user data to be accessible under certain privacy conditions at the cost of accuracy in query results, which is caused by noise. The noise is based on a tuneable constant ε and the global sensitivity of a query. The query sensitivity is defined as the greatest possible difference in query result between the queried database and a neighboring database. Where the neighboring database is defined to differ by one record in a tabular database, there are multiple neighborhood notions for edge-labeled graphs. This thesis considers the notions of edge neighborhood, node neighborhood, QL-edge neighborhood and QL-outedges neighborhood. To study these notions, a framework was developed in Java to function as a query mechanism for a graph database. ArangoDB was used as a storage for graphs, which was generated by parsing data sets in the RDF format as well as through a graph synthesizer in the developed framework. Querying a database in the framework is done with Apache TinkerPop, and a Laplace distribution is used when generating noise for the query results. The framework was used to study the privacy and utility trade-off of different histogram queries on a number of data sets, while employing the different notions of neighborhood in edge-labeled graphs. The level of privacy is determined by the value on ε, and the utility is defined as a measurement based on the L1-distance between the true and noisy result. In the general case, the notions of edge neighborhood and QL-edge neighborhood are the better alternatives in terms of privacy and utility. Although, there are indications that node neighborhood and QL-outedges neighborhood are considerable options for larger graphs, where the level of privacy for edge neighborhood and QL-edge neighborhood appears to be negligible based on utility measurements.

Online social networks pose particular challenges to designing effective algorithms and protocols. Apart from their distributed nature, their behaviour depends on user behaviour and is difficult to test at a realistic scale. Stochastic graph transformation systems can model the operation of such networks but due to the inherent complexity they are hard to analyse. Techniques such as model checking and simulation, which can be used to verify a range of quantitative properties, do not scale well to systems with large graphs and state spaces. Aiming for an efficient alternative, we propose to derive a system of differential equations approximating the average evolution of the network. Variables in these equations represent numbers of occurrences of patterns selected to observe structural features. To keep the number of patterns small, rather than aiming for a fully accurate model we approximate complex patterns by the composition of simpler ones. We describe the approximation and its implementation based on critical pair analysis, illustrate and validate the process by examples of a social network protocol for P2P content policing and a voter model. We will also point out limitations in our approach to approximation and the use of differential equations more generally and discuss how they can be overcome.

La vie privée est une préoccupation des utilisateurs des réseaux sociaux. Les réseaux sociaux sont une source de données précieuses pour des analyses scientifiques ou commerciales. Cette thèse aborde trois problèmes de confidentialité des réseaux sociaux: l'anonymisation de graphes sociaux, la détection de communautés privées et l'échange de liens privés. Nous abordons le problème d'anonymisation de graphes via la sémantique de l'incertitude et l'intimité différentielle. Pour la première, nous proposons un modèle général appelé Uncertain Adjacency Matrix (UAM) qui préserve dans le graphe anonymisé les degrés des nœuds du graphe non-anonymisé. Nous analysons deux schémas proposés récemment et montrons leur adaptation dans notre modèle. Nous aussi présentons notre approche dite MaxVar. Pour la technique d'intimité différentielle, le problème devient difficile en raison de l'énorme espace des graphes anonymisés possibles. Un grand nombre de systèmes existants ne permettent pas de relâcher le budget contrôlant la vie privée, ni de déterminer sa borne supérieure. Dans notre approche nous pouvons calculer cette borne. Nous introduisons le nouveau schéma Top-m-Filter de complexité linéaire et améliorons la technique récente EdgeFlip. L'évaluation de ces algorithmes sur une large gamme de graphes donne un panorama de l'état de l'art. Nous présentons le problème original de la détection de la communauté dans le cadre de l'intimité différentielle. Nous analysons les défis majeurs du problème et nous proposons quelques approches pour les aborder sous deux angles: par perturbation d'entrée (schéma LouvainDP) et par perturbation d'algorithme (schéma ModDivisive)
Privacy is a serious concern of users in daily usage of social networks. Social networks are a valuable data source for large-scale studies on social organization and evolution and are usually published in anonymized forms. This thesis addresses three privacy problems of social networks: graph anonymization, private community detection and private link exchange. First, we tackle the problem of graph anonymization via uncertainty semantics and differential privacy. As for uncertainty semantics, we propose a general obfuscation model called Uncertain Adjacency Matrix (UAM) that keep expected node degrees equal to those in the unanonymized graph. We analyze two recently proposed schemes and show their fitting into the model. We also present our scheme Maximum Variance (MaxVar) to fill the gap between them. Using differential privacy, the problem is very challenging because of the huge output space of noisy graphs. A large body of existing schemes on differentially private release of graphs are not consistent with increasing privacy budgets as well as do not clarify the upper bounds of privacy budgets. In this thesis, such a bound is provided. We introduce the new linear scheme Top-m-Filter (TmF) and improve the existing technique EdgeFlip. Thorough comparative evaluation on a wide range of graphs provides a panorama of the state-of-the-art's performance as well as validates our proposed schemes. Second, we present the problem of community detection under differential privacy. We analyze the major challenges behind the problem and propose several schemes to tackle them from two perspectives: input perturbation (LouvainDP) and algorithm perturbation (ModDivisive)

Thesis (S. M.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2008.
Includes bibliographical references (leaf 53).
In this thesis I study r-differential posets and dual graded graphs. Differential posets are partially ordered sets whose elements form the basis of a vector space that satisfies DU-UD=rI, where U and D are certain order-raising and order-lowering operators. New results are presented related to the growth and classification of differential posets. In particular, we prove that the rank sequence of an r-differential poset is bounded above by the Fibonacci sequence and that there is a unique poset with such a maximum rank sequence. We also prove that a 1-differential lattice is either Young's lattice or the Fibonacci lattice. In the second part of the thesis, we present a series of new examples of dual graded graphs that are not isomorphic to the ones presented in Fomin's original paper.
by Yulan Qing.
S.M.

This thesis consists of two papers, enumerated by Roman numerals. The main focus is on the spectral theory of -Laplacians. Here, an -Laplacian, for integer , refers to a metric graph equipped with a differential operator whose differential expression is the -th derivative. In Paper I, a classification of all vertex conditions corresponding to self-adjoint -Laplacians is given, and for these operators, a secular equation is derived. Their spectral asymptotics are analysed using the fact that the secular function is close to a trigonometric polynomial, a type of almost periodic function. The notion of the quasispectrum for -Laplacians is introduced, identified with the positive roots of the associated trigonometric polynomial, and is proved to be unique. New results about almost periodic functions are proved, and using these it is shown that the quasispectrum asymptotically approximates the spectrum, counting multiplicities, and results about asymptotic isospectrality are deduced. The results obtained on almost periodic functions have wider applications outside the theory of differential operators. Paper II deals more specifically with bi-Laplacians (), and a notion of standard conditions is introduced. Upper and lower estimates for the spectral gap --- the difference between the two lowest eigenvalues - for these standard conditions are derived. This is achieved by adapting the methods of graph surgery used for quantum graphs to fourth order differential operators. It is observed that these methods offer stronger estimates for certain classes of metric graphs. A geometric version of the Ambartsumian theorem for these operators is proved.

This master’s thesis deals with designing of fully-differential current-mode frequency filters using signal-flow graphs method. The first part is focused on a general description of frequency filters, its function and division. Active elements that create these frequency filters, such as multi-output current follower (MO-CF), balanced or multi-output transconductance amplifier (BOTA, MOTA) and digitally adjustace current amplifier (DACA) are described in the following part. Next, problems and various techniques of designing such filters are discussed on a theoretic basis. In the remaining part of the thesis there are six circuits of frequency filters described in detail; these connections are then transferred of passive elements to a proposed connections, with the assistance of a so-called reflection. Calculations of passive form are stated, as well as results of simulations, where nondifferential and differential variations of these designed frequency filters are compared. Finaly, it has been selected some variants of designs, which has been manufactured, then measured out and resulet has been compare between each other.

The dissertation deals with the design of fully differential frequency filters using the signal flow graphs. It presents the procedures for designing frequency filters, focusing on the active elements such as multiple-output current followers (MO-CF) and digitally adjustable current amplifiers (DACA), which work in a current mode. It is theoretically discussed the issue of designing the M-C graphs, which are the graphic analogy of voltage and current incidence matrices. There are also presented three designs of 2nd order frequency filter circuits using the indirect method of design by M-C graphs and one circuit design using the direct method. The results of each simulation and measurement are presented in a module frequency characteristics. Finally, there is a summary of M-C graphs characteristics and applicability.

Let S ⊆ V be an arbitrary subset of vertices of a graph G = (V,E). The differential ∂(S) equals the difference between the cardinality of the set of vertices not in S but adjacent to vertices in S, and the cardinality of the set S. The differential of a graph G equals the maximum differential of any subset S of V . A set S is called a zero set if ∂(S) = 0. In this thesis we introduce the study of zero sets in graphs. We give proofs of the existence of zero sets in various kinds of graphs such as even order graphs, bipartite graphs, and graphs of maximum degree 3. We also give proofs regarding the existence of graphs which contain no zero sets and the construction of zero-free graphs from graphs which contain zero sets.

La géostatistique est la branche des statistiques s’intéressant à la modélisation des phénomènes ancrés dans l’espace au travers de modèles probabilistes. En particulier, le phénomène en question est décrit par un champ aléatoire (généralement gaussien) et les données observées sont considérées comme résultant d’une réalisation particulière de ce champ aléatoire. Afin de faciliter la modélisation et les traitements géostatistiques qui en découlent, il est d’usage de supposer ce champ comme stationnaire et donc de supposer que la structuration spatiale des données se répète dans le domaine d’étude.Cependant, lorsqu’on travaille avec des jeux de données spatialisées complexes, cette hypothèse devient inadaptée. En effet, comment définir cette notion de stationnarité lorsque les données sont indexées sur des domaines non euclidiens(comme des sphères ou autres surfaces lisses)? Quid également du cas où les données présentent structuration spatiale qui change manifestement d’un endroit à l’autre du domaine d’étude? En outre, opter pour des modèles plus complexes,lorsque cela est possible, s’accompagne en général d’une augmentation drastique des coûts opérationnels (calcul et mémoire), fermant alors la porte à leur application à de grands jeux de données. Dans ce travail, nous proposons une solution à ces problèmes s’appuyant sur la définition de champs aléatoires généralisés sur des variétés riemanniennes. D’une part, travailler avec des champs aléatoires généralisés permet d’étendre naturellement des travaux récents s’attachant à tirer parti d’une caractérisation des champs aléatoires utilisés en géostatistique comme des solutions d’équations aux dérivées partielles stochastiques. D’autre part, travailler sur des variétés riemanniennes permet à la fois de définir des champs sur des domaines qui ne sont que localement euclidiens, et sur des domaines vus comme déformés localement (ouvrant donc la porte à la prise en compte du cas non stationnaire). Ces champs généralisés sont ensuite discrétisés en utilisant une approche par éléments finis, et nous en donnons une formule analytique pour une large classe de champs généralisés englobant les champs généralement utilisés dans les applications. Enfin, afin de résoudre le problème du passage à l’échelle pour les grands jeux de données, nous proposons des algorithmes inspirés du traitement du signal sur graphe permettant la simulation, la prédiction et l’inférence de ces champs par des approches "matrix-free"
Geostatistics is the branch of statistics attached to model spatial phenomena through probabilistic models. In particular, the spatial phenomenon is described by a (generally Gaussian) random field, and the observed data are considered as resulting from a particular realization of this random field. To facilitate the modeling and the subsequent geostatistical operations applied to the data, the random field is usually assumed to be stationary, thus meaning that the spatial structure of the data replicates across the domain of study. However, when dealing with complex spatial datasets, this assumption becomes ill-adapted. Indeed, how can the notion of stationarity be defined (and applied) when the data lie on non-Euclidean domains (such as spheres or other smooth surfaces)? Also, what about the case where the data clearly display a spatial structure that varies across the domain? Besides, using more complex models (when it is possible) generally comes at the price of a drastic increase in operational costs (computational and storage-wise), rendering them impossible to apply to large datasets. In this work, we propose a solution to both problems, which relies on the definition of generalized random fields on Riemannian manifolds. On one hand, working with generalized random fields allows to naturally extend ongoing work that is done to leverage a characterization of random fields used in Geostatistics as solutions of stochastic partial differential equations. On the other hand, working on Riemannian manifolds allows to define such fields on both (only) locally Euclidean domains and on locally deformed spaces (thus yielding a framework to account for non-stationary cases). The discretization of these generalized random fields is undertaken using a finite element approach, and we provide an explicit formula for a large class of fields comprising those generally used in applications. Finally, to solve the scalability problem,we propose algorithms inspired from graph signal processing to tackle the simulation, the estimation and the inference of these fields using matrix-free approaches

La théorie des jeux à champ moyen fut introduite en 2006 par Jean-Michel Lasry et Pierre-Louis Lions. Elle permet l'étude de la théorie des jeux dans certaines configurations où le nombre de joueurs est trop grand pour espérer une résolution pratique. Nous étudions la théorie des jeux à champ moyen sur les graphes en nous appuyant sur les travaux d'Olivier Guéant que nous étendrons à des formes plus générales d'Hilbertien. Nous étudierons aussi les liens qui existent entres les K-moyennes et les jeux à champ moyen ce qui permettra en principe de proposer de nouveaux algorithmes pour les K-moyennes grâce aux techniques de résolution numérique propres aux jeux à champ moyen. Enfin nous étudierons un jeu à champ moyen à savoir le problème "d'heure de début d'une réunion" en l'étendant à des situations où les agents peuvent choisir entre deux réunions. Nous étudierons de manière analytique et numérique l'existence et la multiplicité des solutions de ce problème
The mean field game theory was introduced in 2006 by Jean-Michel Lasry and Pierre-Louis Lions. It allows us to study the game theory in some situations where the number of players is too high to be able to be solved in practice. We will study the mean field game theory on graphs by learning from the studies of Oliver Guéant which we will extend to more generalized forms of Hilbertian. We will also study the links between the K-means and the mean field game theory. In principle, this will offer us new algorithms for solving the K-means thanks to the techniques of numerical resolutions of the mean field games. Findly, we will study a mean field game called the "starting time of a meeting". We will extend it to situations where the players can choose between two meetings. We will study analytically and numerically the existence and multiplicity of the solutions to this problem

Les données numériques jouent un rôle crucial dans notre vie quotidienne en communiquant, en enregistrant des informations, en exprimant nos pensées et nos opinions et en capturant nos moments précieux sous forme d'images et de vidéos numériques. Les données numériques présentent d'énormes avantages dans tous les aspects de la vie moderne, mais constituent également une menace pour notre vie privée. Dans cette thèse, nous considérons trois types de données numériques en ligne générées par les utilisateurs des médias sociaux et les clients du commerce électronique : les graphiques, les transactions et les images. Les graphiques sont des enregistrements des interactions entre les utilisateurs qui aident les entreprises à comprendre qui sont les utilisateurs influents dans leur environnement. Les photos postées sur les réseaux sociaux sont une source importante de données qui nécessitent des efforts d'extraction. Les ensembles de données transactionnelles représentent les opérations qui ont eu lieu sur les services de commerce électronique.Nous nous appuyons sur une technique de préservation de la vie privée appelée Differential Privacy (DP) et sa généralisation Blowfish Privacy (BP) pour proposer plusieurs solutions permettant aux propriétaires de données de bénéficier de leurs ensembles de données sans risque de violation de la vie privée pouvant entraîner des problèmes juridiques. Ces techniques sont basées sur l'idée de récupérer l'existence ou la non-existence de tout élément dans l'ensemble de données (tuple, ligne, bord, nœud, image, vecteur, ...) en ajoutant respectivement un petit bruit sur la sortie pour fournir un bon équilibre entre intimité et utilité.Dans le premier cas d'utilisation, nous nous concentrons sur les graphes en proposant trois mécanismes différents pour protéger les données personnelles des utilisateurs avant d'analyser les jeux de données. Pour le premier mécanisme, nous présentons un scénario pour protéger les connexions entre les utilisateurs avec une nouvelle approche où les utilisateurs ont des privilèges différents : les utilisateurs VIP ont besoin d'un niveau de confidentialité plus élevé que les utilisateurs standard. Le scénario du deuxième mécanisme est centré sur la protection d'un groupe de personnes (sous-graphes) au lieu de nœuds ou d'arêtes dans un type de graphes plus avancé appelé graphes dynamiques où les nœuds et les arêtes peuvent changer à chaque intervalle de temps. Dans le troisième scénario, nous continuons à nous concentrer sur les graphiques dynamiques, mais cette fois, les adversaires sont plus agressifs que les deux derniers scénarios car ils plantent de faux comptes dans les graphiques dynamiques pour se connecter à des utilisateurs honnêtes et essayer de révéler leurs nœuds représentatifs dans le graphique.Dans le deuxième cas d'utilisation, nous contribuons dans le domaine des données transactionnelles en présentant un mécanisme existant appelé Safe Grouping. Il repose sur le regroupement des tuples de manière à masquer les corrélations entre eux que l'adversaire pourrait utiliser pour violer la vie privée des utilisateurs. D'un autre côté, ces corrélations sont importantes pour les propriétaires de données dans l'analyse des données pour comprendre qui pourrait être intéressé par des produits, biens ou services similaires. Pour cette raison, nous proposons un nouveau mécanisme qui expose ces corrélations dans de tels ensembles de données, et nous prouvons que le niveau de confidentialité est similaire au niveau fourni par Safe Grouping.Le troisième cas d'usage concerne les images postées par les utilisateurs sur les réseaux sociaux. Nous proposons un mécanisme de préservation de la confidentialité qui permet aux propriétaires des données de classer les éléments des photos sans révéler d'informations sensibles. Nous présentons un scénario d'extraction des sentiments sur les visages en interdisant aux adversaires de reconnaître l'identité des personnes
Digital data is playing crucial role in our daily life in communicating, saving information, expressing our thoughts and opinions and capturing our precious moments as digital pictures and videos. Digital data has enormous benefits in all the aspects of modern life but forms also a threat to our privacy. In this thesis, we consider three types of online digital data generated by users of social media and e-commerce customers: graphs, transactional, and images. The graphs are records of the interactions between users that help the companies understand who are the influential users in their surroundings. The photos posted on social networks are an important source of data that need efforts to extract. The transactional datasets represent the operations that occurred on e-commerce services.We rely on a privacy-preserving technique called Differential Privacy (DP) and its generalization Blowfish Privacy (BP) to propose several solutions for the data owners to benefit from their datasets without the risk of privacy breach that could lead to legal issues. These techniques are based on the idea of recovering the existence or non-existence of any element in the dataset (tuple, row, edge, node, image, vector, ...) by adding respectively small noise on the output to provide a good balance between privacy and utility.In the first use case, we focus on the graphs by proposing three different mechanisms to protect the users' personal data before analyzing the datasets. For the first mechanism, we present a scenario to protect the connections between users (the edges in the graph) with a new approach where the users have different privileges: the VIP users need a higher level of privacy than standard users. The scenario for the second mechanism is centered on protecting a group of people (subgraphs) instead of nodes or edges in a more advanced type of graphs called dynamic graphs where the nodes and the edges might change in each time interval. In the third scenario, we keep focusing on dynamic graphs, but this time the adversaries are more aggressive than the past two scenarios as they are planting fake accounts in the dynamic graphs to connect to honest users and try to reveal their representative nodes in the graph. In the second use case, we contribute in the domain of transactional data by presenting an existed mechanism called Safe Grouping. It relies on grouping the tuples in such a way that hides the correlations between them that the adversary could use to breach the privacy of the users. On the other side, these correlations are important for the data owners in analyzing the data to understand who might be interested in similar products, goods or services. For this reason, we propose a new mechanism that exposes these correlations in such datasets, and we prove that the level of privacy is similar to the level provided by Safe Grouping.The third use-case concerns the images posted by users on social networks. We propose a privacy-preserving mechanism that allows the data owners to classify the elements in the photos without revealing sensitive information. We present a scenario of extracting the sentiments on the faces with forbidding the adversaries from recognizing the identity of the persons. For each use-case, we present the results of the experiments that prove that our algorithms can provide a good balance between privacy and utility and that they outperform existing solutions at least in one of these two concepts

The aim of this MSc Thesis is to create a system for automatic generation of frequency characteristics of electrical circuits. These circuits are described by differential equations. A special simulator of RLC circuit has been created and frequence response, vector diagram can be generated. This system has been mainly suggested for application in education. The process of solving differential equations is based on the Taylor method. Systems in general is the theoretical part of this project. Different definitions of systems their divission ,basic phenomenons and mathematical devices are described there. Next chapter deals with the mathematical devices for solving differential equations which makes the basis for description of phenomenons in these systems. There are also systems TKSL and TKSL/C. In the next chapter I was investigaty the analyze of vector diagrams for simple and more difficult circuits. I have found a solution for actual circuit by this technique. The last chapter is devoted to the frequency characteristics and descriptions of simulation program for generation the frequency characteristics.

Dans le cadre de la géométrie riemannienne globale sans hypothèse de courbure en lien avec la topologie, nous nous intéressons au volume maximal des boules de rayon fixé dans les revêtements universels des graphes et des surfaces. Dans la première partie, nous prouvons que si l'aire d'une surface riemannienne fermée M de genre au moins 2 est suffisamment petite par rapport à son aire hyperbolique, alors pour chaque rayon R>0, le revêtement universel de M contient une R-boule d'aire au moins l'aire d'une cR-boule dans le plan hyperbolique, où c<1 est une constante universelle. En particulier (quitte à prendre l'aire de la surface encore plus petite), nous démontrons que pour chaque rayon R plus grand ou égal à 1, le revêtement universel de M contient une R-boule d'aire au moins l'aire d'une R-boule dans le plan hyperbolique. Ce résultat répond positivement pour les surfaces, à une question de L. Guth. Nous démontrons également que si Gamma est un graphe connexe de premier nombre de Betti b et de longueur su suffisamment petite par rapport à la longueur d'un graphe trivalent Gamma_b de premier nombre de Betti b dont la longueur de chaque arête est 1, alors pour chaque rayon R>0, le revêtement universel de Gamma contient une R-boule d'aire au moins c fois l'aire d'une R-boule dans le revêtement universel de Gamma_b, où c est dans l'intervalle (1/2 ,1). Dans la deuxième partie, nous généralisons un théorème de M. Gromov concernant le nombre maximal de courts lacets homotopiquement indépendants basés en un même point. Plus précisément, nous prouvons que sur toute surface riemannienne fermée M de genre g et d'aire normalisée à g, il existe au moins log(2g) lacets homotopiquement indépendants basés en un même point de longueur au plus C log(g), où C est une constante positive indépendante du genre. Comme corollaire immédiat de ce théorème, nous redémontrons l'inégalité systolique asymptotique sur la systole séparante. Nous démontrons également un théorème analogue pour les graphes métriques. Plus précisément, nous prouvons que sur chaque graphe métrique Gamma de premier nombre de Betti b et de longueur b, il existe au moins log(b) lacets homologiquement indépendants basés en un même point de longueur au plus 48 log(b). Ce résultat étend la borne en log(b) sur la systole homologique dûe à Bollobàs-Szemerédi-Thomason à au moins log(b) lacets homologiquement indépendants basés en un même point. En outre, nous donnons des exemples de graphes où notre résultat est optimal (à une constante multiplicative près).

We study the maximum differential coloring problem, where an n-vertex graph must be colored with colors numbered 1, 2...n such that the minimal difference between the two colors of any edge is maximized. This problem is motivated by coloring maps in which not all countries are contiguous. Since it is known that this problem is NP-hard for general graphs; we consider planar graphs and subclasses thereof. In Chapter 1 we introduce the topic of this thesis and in Chapter 2 we review relevant definitions and basic results. In Chapter 3 we prove that the maximum differential coloring problem remains NP-hard even for planar graphs. Then, we present tight bounds for regular caterpillars and spider graphs and close-to-optimal differential coloring algorithms for general caterpillars and biconnected triangle-free outer-planar graphs. In Chapter 4 we introduce the (d, kn)-differential coloring problem. While it was known that the problem of determining whether a general graph is (2, n)-differential colorable is NP-complete, in this chapter we provide a complete characterization of bipartite, planar and outerplanar graphs that admit (2, n)-differential colorings. We show that it is NP-complete to determine whether a graph admits a (3, 2n)-differential coloring. The same negative result holds for the ([2n/3], 2n)-differential coloring problem, even when input graph is planar. In Chapter 5 we experimentally evaluate and compare several algorithms for coloring a map. Motivated by different application scenarios, we classify our approaches into two categories, depending on the dimensionality of the underlying color space. To cope with the one dimensional color space (e.g., gray-scale colors), we employ the (d, kn)-differential coloring. In Chapter 6 we describe a practical approach for visualizing multiple relationships defined on the same dataset using a geographic map metaphor, where clusters of nodes form countries and neighboring countries correspond to nearby clusters. The aim is to provide a visualization that allows us to compare two or more such maps. In the case where we are considering multiple relationships we also provide an interactive tool to visually explore the effect of combining two or more such relationships. Our method ensures good readability and mental map preservation, based on dynamic node placement with node stability, dynamic clustering with cluster stability, and dynamic coloring with color stability. Finally in Chapter 7 we discuss future work and open problems.

Cette thèse a pour but l'étude de la propriété de platitude sur des modèles bond graphs (BGs) non linéaires et de contribuer à la résolution des problèmes rencontrés en pratique qui sont liés principalement à l'identification des sorties plates et le calcul de la paramétrisation différentielle.
Pour atteindre cet objectif, de nouveaux concepts et outils graphiques ont été introduits. En particulier, grâce à l'introduction de la notion de modèle BG tangent ou variationnel à l'aide de l'utilisation des différentielles de Kähler, il est possible de calculer les sorties plates d'un modèle BG non linéaire par intégration des bases du module qui lui est associé.
Par ailleurs, en définissant la notion d'anneau BG non commutatif, une nouvelle règle de gain connue sous le nom de "règle de Riegle" est introduite en BG. En montrant alors qu'un modèle BG variationnel est un cas particulier d'anneau BG non commutatif, l'obtention graphique de la paramétrisation différentielle en utilisant la règle de Riegle et la notion de bicausalité est rendue possible.
Enfin, pour aller plus loin dans l'introduction de l'outil d'algèbre et de modules différentiels aux BGs, le cas des modèles BGs non linéaires régis par des équations différentielles polynômiales a été abordé. Dans ce contexte, le BG permet de faire une analyse directe des propriétés principales du système telles que le choix des variables d'entrée, les dynamiques correspondant à un choix d'entrée, le calcul des degrés de transcendance (non différentiel) différentiel, etc. à partir de son modèle BG associé. Il est également montré que la règle graphique de Riegle peut être étendue à cette classe de modèles BGs.

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires.

Cilj  ove  doktorske  disertacije  je  bio  razvoj  brzih  i  pouzdanih  voltametrijskih  metoda zasnovanih na primeni jednostavnih i savremenih elektroda/senzora na bazi ugljeničnih materijala (ugljenične  paste  napravljene  od  grafitnog  praha  i  parafinskog  ulja  i  štampanih  ugljeničnih elektroda)  za  određivanje  H ₂O₂ u  odabranim  složenim  model  i  realnim  uzorcima.  U  tu  svrhu, ispitana je primenljivost različitih radnih elektroda. Amperometrijska  metoda  zasnovana  na  elektrodi  od  ugljenične  paste  (CPE)  zapreminski modifikovane  sa  5%  (m:m)  MnO2 je,  pri  optimizovanim  uslovima  i  pri  radnom  potencijalu  od 0,40 V  u  odnosu  na  zasićenu  kalomelovu  elektrodu  (ZKE)  u  fosfatnom  puferu  pH  7,50  kao pomoćnom elektrolitu, omogućila kvantifikaciju H ₂O₂ u opsegu koncentracija od 1,4 do 65 µg mL -1 sa  relativnom  standardnom  devijacijom  (RSD)  manjom  od  10%.  Ova  metoda  je  primenjena  za određivanje sadržaja H ₂O₂ u uzorcima podzemne vode iz centralnog Banata (Pokrajina Vojvodina, Srbija)  tretirane  Fentonovim  (Fe ²⁺ i  H ₂O₂ )  i  Fentonu-sličnim  (Fe ³⁺ i  H ₂O₂ )  reagensima  u  cilju uklanjanja  prirodnih  organskih  materija  (POM)  pri  čemu  su  korišćene  različite  početne koncentracije  gvožđa  i  različiti  odnosi  molarnih  koncentracija  gvožđa  i  H ₂O₂ .  Utvrđeno  je  da oksidaciono  stanje  gvožđe  (Fe ²⁺ ili  Fe ³⁺)  i  molarni  odnos  jona  Fe  i  H ₂O₂ utiču  na  stepen potrošnje/razgradnje  H ₂O₂u  podzemnoj  vodi  sa  visokim  sadržajem  POM.  Takođe,  u  slučaju Fentonu-sličnog  procesa,  za  sve  početne  koncentracije  Fe ³⁺ i  H ₂O_{2 ,}  signifikantna  količina  H ₂O₂ ostaje  neiskorišćena,  što  ukazuje  na  nižu  efikasnost  ovakvog  sistema u  poređenju  sa  Fentonovim procesom.Štampana  ugljenična  elektroda  (SPCE)  zapreminski  modifikovana  sa  MnO 2 kao medijatorom  je  primenjena  za  određivanje  sadržaja  H ₂O₂ u  toku  Fentonovog  (Fe ²⁺ ,  H₂O₂ )  i vidljivom  svetlošću  potpomognutog  foto-Fentonovog  (Fe ²⁺ ,  H ₂O₂ ,  hν)  procesa  uklanjanja neonikotinoidnog  insekticida  acetamiprida  (ACT).  Pri  optimizovanim  uslovima  (radni  potencijal 0,40  V  u  odnosu  na  ZKE,  fosfatni  pufer  pH  7,50  kao  pomoćni  elektrolit)  amperometrijskog određivanja  H ₂O₂ ,  postignuta  je  linearnost  u  opsegu  koncentracija  0,01–1,24  mmol  L-1(0,34– 42,2 µg mL -1) i vrednost RSD nije prelazila 4,2%. U ispitivanimuzorcima (nakon odgovarajućegpodešavanja pH vrednosti od 2,8 do 7,5 odmah nakon  uzorkovanja radi stopiranja ili maksimalnog usporavanja  procesa  oksidacije,  filtriranja,  zamrzavanja  i  odmrzavanja  neposredno  pre  merenja) sadržaj  H ₂O₂ je  određen  metodom  standardnog  dodatka  analiziranjem  odgovarajućih amperometrijskih  krivi.  Paralelna  HPLC-DAD  merenja  su  vršena  u  cilju  praćenja koncentracije/uklanjanja ACT. U slučaju foto-Fentonovog procesa (početne koncentracije 0,31; 2,0 i 3,0 mmol L -1 (70,0; 111,7 i 102,1 µg mL -1 ) za ACT, Fe²⁺ i H ₂O₂, redom) nakon 10 min H ₂O₂ je izreagovao, a može se smatrati da je ACT uklonjen nakon 5 min. U toku Fentonovog procesa ACT je  uklonjen  nakon  20  min  tretmana  i  oko  10%  početne  koncentracije  H ₂O₂ je  ostalo  u  sistemuneiskorišćeno.CPE  je  površinski  modifikovane  kompozitom  na  bazi  nanočestica  Pt  (<  5  nm)  i grafitizovanog  ugljenika  (Pt-C,  10%  Pt  na  Vulkanu  XC72)   etodom  nanošenja  kapi. Nemodifikovana  CPE  i  modifikovana  (Pt-C/CPE)  su   okarakterisane  primenom  SEM/EDS  i  CV merenja.  Pt-C/CPE  je  pokazala  izuzetne  elektrokatalitičke  osobine  u  pogledu  elektrohemijskeredoks  reakcije  H₂O₂ u  poređenju  sa  nemodifikovanom  CPE  u  fosfatnom  puferu  (0,1 mol  L -1 ;pH 7,50),  a  takođe  i  u  acetatnom  puferu  (0,1  mol  L -1 ;  pH  4,50)  kao   pomoćnim  elektrolitima. Prilikom  amperometrijskog  određivanja  H ₂O₂ primenom  Pt-C/CPE  u  model  sistemima, zadovoljavajuća linearnost je postignuta u koncentracionom opseguH₂O₂od 0,15 do 1,45 µg mL -1 ,dok su vrednosti GO iznosile 0,06 µg mL -1 (pH 7,50, radni potencijal 0,20 V) i 0,10 µg mL -1 (pH4,50,  radni  potencijal  0,50  V).  Optimizovane  analitičke  metode  su  primenjene  za  određivanje sadržaja H ₂O₂ u komercijalno dostupnim proizvodima za ličnu negu: rastvoru za dezinfekciju (pH 7,50)  i  rastvoru  za  čišćenje  kontaktnih  sočiva  (pH  4,50).  Amperometrijski  dobijeni  rezultati  su  u dobrom  slaganju  sa  rezultatima  dobijenim  primenom  tradicionalne  spektrofotometrijske  metode bazirane  na  titanijum-sulfatu  kao  reagensu  sa  određenim  koncentracijama  2,91%  i  2,94%  zadezinfekcioni rastvor i 3,04% i 3,17% za rastvor zakontaktna sočiva, redom. RSD je bila manja od 2%.  Postignuti  rezultati  su  u  dobrom  slaganju  sa  sadržajem  H₂O₂ deklarisanim  od  strane proizvođača (3%) u oba ispitivana uzorka. Pt-C/CPE je takođe testirana za praćenje koncentracije H₂O₂ u rastvoru za kontaktna sočiva u toku procesa njegove neutralizacije/razgradnje. Nakon 6 h procesa neutralizacije, 24,68  µg mL -1 je bila određena koncentracija H ₂O_{2 ,} što je ispod dozvoljeneH₂O₂ koncentracije u rastvoru za kontaktna sočiva imajući u vidu granicu koja izaziva iritaciju oka. CPE  je  površinski  modifikovana  višezidnim  ugljeničnim  nanocevima  (MWCNT)  i kompozitima MnO 2 -MWCNT ili Pt-MWCNT metodom nanošenja kapi radi pripreme jednostavnih, osetljivih i pouzdanih voltametrijskih senzora za  određivanje H ₂O₂ u odabranom uzorku. Rezultati SEM/EDS  analize  kompozitnih  materijala  su  potvrdili da  su  medijatori,  čestice  MnO 2 i  Pt, nasumično  raspoređeni na površini MWCNT i zastupljeni sa blizu 5% (m:m) u kompozitu izraženopreko Mn i Pt. CV merenja su vršena sa pripremljenim radnim elektrodama u acetatnom (pH 4,50), fosfatnom  (pH  7,50)  i  boratnom  (pH  9,18)  puferu  kako  bi  se  okarakterisalo  osnovno elektrohemijsko  ponašanje  H ₂O₂ i  odabrali  pogodni  radni  potencijali  za  amperometrijsko određivanje ovog ciljnog analita. Pt- WCNT/CPE je primenljiva za rad kako u fosfatnom puferu pH  7,50  tako  i  u  acetatnom  puferu  pH  4,50  V  kako  pri  negativnim  tako  i  pri  pozitivnim  radnimpotencijalima, pri  čemu su vrednosti RSD uglavnom ispod 2,5%. U slučaju MnO 2-MWCNT/CPE, na  potencijalu  0,30  V  i  višim  vrednostima,  oksidacioni  signali  H₂O₂ su  signifikantni  u  blago alkalnoj sredini (pH 7,50), pri pH 4,50 ova elektroda pokazuje nezadovoljavajuće ponašanje, dok  pri pH 9,18 ima prihvatljive performanse. Granice određivanja (GO) su bile u oblasti µg mL -1 . H ₂O₂ je  određen  u  spajkovanom  uzorku  mleka  metodom  standardnog  dodatka  nakon  odgovarajuće pripreme  uzorka  (pH  podešavanje  i  centrifugiranje)  i  primenom  optimizovane  amperometrijske procedure (acetatni pufer pH 4,50, radni  potencijal-0,75 V) koristeći Pt-MWCNT/CPE kao radnu elektrodu. RSD za tri  ponovljena merenja je iznosila 2,5%, dok je prinos metode bio nešto veći od 71%.Kompozitni materijali koji se sastoje od MWCNT i  čestica na bazi Pd (Pd-MWCNT) ili Pt (Pt-MWCNT) su primenjeni za pripremu zapreminski modifikovanih SPCE (Pd-MWCNT-SPCE i Pt-MWCNT-SPCE)  i  površinski  modifikovane  SPCE  (Pd-MWCNT/SPCE).  Ove  elektrode,  kao  i nemodifikovana  SPCE  i  MWCNT-SPCE,  su  okarakterisane primenom  CV  i  amperometrije  u fosfatnom puferu pH 7,50 radi određivanja H ₂O₂ . Pd-MWCNT-SPCE i Pd-MWCNT/SPCE su se pokazale  pogodnim  za  određivanje  H ₂O₂ na  radnim  potencijalima  između  -0,50  i  0,50  V,  a  PtMWCNT-SPCE na ispitivanim radnim potencijalima od -0,80 do 0,70 V. Ove  elektrode su zatim modifikovane  enzimom  glukoza  oksidazom  (GOx)  metodom  nanošenja  kapi  rastvora  GOx  i Nafion ® -a  na  njihovu  površinu,  pri  čemu  je  optimizovana  količina  nanetog  biofilma.  GOx/PdMWCNT-SPCE  je  pokazala  bolje  analitičke  performanse  za  određivanje  glukoze  u  poređenju  sa GOx/Pd- WCNT/SPCE.  Kao  optimalan  radni  potencijal  GOx/Pd-MWCNT-SPCE  je  odabranavrednost  potencijala  -0,40  V  u  odnosu  na  ZKE,  sa  zadovoljavajućom  linearnošću  u  ispitivanom opsegu  koncentracija  glukoze  od  0,16  do  0,97  mmol  L -1 (od  29,1  do  174  µg  mL -1),  dok  je  GO iznosila 0,14 mmol L -1 (25 µg mL-1 ). Optimizovana metoda zasnovana na GOx/Pd-MWCNT-SPCE je  uspešno  primenjena  za  određivanje  glukoze  u  uzorku  livadskog  meda.  Dobijeni  rezultati  su  u dobroj  saglasnosti  sa  onima  dobijenim  primenom  komercijalno  dostupnog  aparata  za  merenje glukoze. Pogodan radni potencijal za GOx/Pt-MWCNT-SPCE je bio -0,50 V u odnosu na ZKE, pri čemu je zadovoljavajuća linearnost postignuta u ispitivanom opsegu koncentracija glukoze od 65,8 do 260,6 µg mL -1 , sa GO 35 µg mL -1 . Optimizovana metoda zasnovana na GOx/Pt-MWCNT-SPCE je  uspešno  primenjena  za  određivanje  glukoze  u  u  uzorku  belog  grožđa  i  uzorku  tableta (Traubenzucker-bonbons),  pri  čemu  su  dobijeni  rezultati  u  dobroj  saglasnosti  sa  rezultatima dobijenim primenom Accu-Chek aparata.Na  osnovu  dobijenih  rezultata  može  se  zaključiti  da  su  razvijene  analitičke  metode  pre svega jednostavne, pouzdane i pogodne za dobijanje brzih informacija o sadržaju H ₂O₂ u različitim tipovima  uzoraka.  Svakako  odabir  pogodne  radne  elektrode,  kao  i  optimizacija  eksperimentalnih uslova su ključni faktori za uspešno određivanje H ₂O₂
null
The aim of this doctoral dissertation was the development of fast and reliable voltammetric methods  based  on  the  application  of  simple  and  contemporary  electrodes/sensors  based  on carbonaceous materials (carbon paste made of graphite powder and paraffin oil and screen printed carbon electrodes) for the determination of H  ₂ O₂ in the selected complex model and real samples.For this purpose, applicability of different working electrodes was investigated.The  amperometric  method  based  on  carbon  paste  electrode  (CPE)  bulk- modified     with 5% (m:m) MnO 2 , under optimized conditions, with a working potential of 0.40 V vs. the saturated calomel  elect rode  (SCE)  and  a  phosphate  buffer  solution  (pH  7.50)  as  supporting  electrolyte, enabled the quantitation of H  ₂ O₂in the concentration interval from 1.4 to 65 µg mL −1 with a relative standard deviation (RSD) of less than 10%. This meth od was applied for the determination of the H ₂ O₂ consumption  in  samples  of  groundwater  fro m  the  Central  Banat  region  (Province  of Vojvodina, Serbia) treated by the Fenton (Fe ²⁺ and H ₂O₂ ) and Fenton-  like (Fe ³⁺and H ₂O₂ ) reagents to remove natural organic matter (NOM) at  differentinitial concentrations of iron species, and of their molar ratios to the initial concentration of H₂O₂ . It was found that the form of Fe (Fe ²⁺ or Fe ³⁺ )and the molar  ratio to H ₂O₂influenced the degree of the H ₂O₂ decomposition in the groundwater with high NOM content. Besides, in the case of the Fenton-like process, for all initial doses of Fe ³⁺ and H  ₂ O₂, a sign ificant amount of H  ₂ O₂ remained unused, whi ch also indicates a lower efficiency of such system compared to the Fenton process. Screen  printed  carbon  electrode  (SPCE)  bulk-modified  with  MnO  ₂ as  a  mediator  was applied  for  amperometric  determination  of  the  H  ₂ O₂ content  during  the  Fenton  (Fe ²⁺ ,  H  ₂ O₂ )  and  visible  light-assisted ,  photo-Fenton  (Fe ²⁺  ,  H  ₂ O₂ ,  hν)   based  removal  of  neonicotinoid  insecticide acetamiprid (ACT). Under  optimized conditions (working potential of 0.40 V vs. SCE, phosphate buffer  pH  7.50  as  supporting  electrolyte)  amperometric  determination  of  H  ₂ O₂ showed  a  linear dynamic range from 0.01 to 1.24 mmol L -1 (from 0.34 to 42.2 µg mL -1) and the RSD did not exceed 4.2%. In the investigated samples (after appropriate pH adjustment from 2.8 to 7.5 instantly after the sampling  to stop or maximum decelerate the oxidation processes, filtering, and storage of the deep- frozen sample with defrosting immediately before the measurements) the H  ₂ O₂  contents were determined by the standard addition method by analyzing the corresponding amperometric curves. Parallel HPLC-DAD measurements were performed to monito r the concentration/removal of ACT. In the case of the photo- Fenton process (initial concentrations: 0.31; 2.0 and 3.0 mmol L -1 (70.0; 111.7 and 102.1 µg mL -1 ) of ACT, Fe ²⁺ and H  ₂ O₂, respec tively) after 10 min of irradiation H  ₂ O₂ was  consumed  and  it  can  be  consi dered  that  ACT  was  removed  after  5  min.  During  the  Fenton process ACT was removed after 20 min of treatment and around 10% of the initial concentration of the H 2O2 remained still unused.CPE  was  surface  modified  with  a  composite  of  Pt  nanoparticles  (<  5  nm)  on  graphitized carbon (Pt-C, 10% Pt on Vulcan XC72) by simply dropcoating method. The unmodified CPE and the  modified  one  (Pt-C/CPE)  were  characterized  by   EM/EDS  and  CV  measurements.  The  PtC/CPE showed remarkable electrocatalytic propertiestoward the electrochemical redox reaction of H ₂ O₂ compared to  modified CPE in phosphate buffer (0.1 mol L -1 ; pH 7.50), as well in acetatebuffer  (0.1 mol  L -1 ; pH .50) supporting  electrolytes. Amperometry of  H2O2 in the concentration range from 0.15 to 1.45 µg mL -1 with the Pt-C/CPE showed acceptable linearity, while the obtained values of LOQs were 0.06 µg mL -1  (pH 7.50, working potential 0.20 V) and 0.10 µg mL -1 (pH 4 .50, working potential 0.50 V). The proposed analytical  methods were applied to the determination of the H 2O2 content in commercially available personal care products; i.e., disinfection (pH 7.50) and contact lens cleaning solutions (pH 4.50). The obtained amperometric results are in good agreement with those measured by traditional titanium sulfatereagent based spectrophotometric method with determined concentrations as 2.91% and 2.94%  for the disinfection product, and 3.04% and 3.17% for the contact lens solution, respectively. RSD was lower than 2%. The obtained results are in a good agreement with the amounts of the H  ₂ O₂ declared by producers (3%) in the both investigated samples. The Pt-C/CPE was also tested for monitoring of the H  ₂ O₂ residual concentration in contact lens  solution  during  its  neutralization/decomposition  rocess.  At  6  h  of   neutralization  treatment 24.68 µg mL -1 of the H  ₂ O₂ was  determined which is almost half of the allowedH2 O2 concentration in the case of the contact lens solution concerningthe limit of eye irritation. CPE  was  surface   modified  with  multiwalled  carbon  nanotubes  (MWCNT)  and  with composites of MnO ₂ -MWCNT or Pt-MWCNT by drop coating method to prepare simply, sensitive and reliable volta mmetric sensors for the determination of H  ₂ O₂ in selected sample. The results of the  SEM/ EDS  analysis  of  composite  materials  have  confirmed  that  the  mediators,  MnO ₂ and  Pt  articles, are randomly distributed on the surface of MWCNT and represent nearly 5% (m:m) of the composite expressed as Mn and Pt. CV measurements were performed  with prepared electrodes in acetate  (pH  4.50),  phosphate  (pH  7.50)  and  borate  (pH  9.18)  buffers  to  characterize  the  basic electrochemical  behavior  of  H  ₂ O₂ and  to  select  the  working  potentials  suitable  for  amperometric determination  of  this  target  analyte.  The  Pt-MWCNT/CPE  performs  well  in  phosphate  buffer pH .50 and acetate buffer solution pH 4.50 in the  negative as well as in the positive polarization range with RSD mainly lower than 2.5%. In case of MnO ₂ -MWCNT/CPE at  0.30 V and above the H ₂ O₂ oxidation signal is rem arkable in slightly alkaline media (pH 7.50), at pH 4.50 this electrode showed poor behavior and at pH 9.18 offered acceptable performance. LOQs were in the µg mL -1 concentration  range.  H ₂ O₂ was  determined  in  a  spiked  milk  sample  by  standard addition  method after  appropriate  sample  preparation  (pH  adjustment and  centrifugation)  and  using  optimized amperometric p rocedure (acetate buffer pH 4.50, working potential -0.75 V) by Pt-MWCNT/CPE as a working electrode. RSD for three repeated measurements was 2.5%, while the recovery of the method was a bit higher than 71%. The  composite  materials  consisting  of  MWCNT  and  Pd  (Pd-MWCNT)  or  Pt  containing particles  (Pt-WCNT)  were  applied  to  the  preparation  of  bulk- modified  SPCEs  (Pd-MWCNTSPCE and Pt-MWCNT-SPCE) and surface modifiedSPCE (Pd- MWCNT/SPCE). These electrodes, as well as unmodified SPCE and MWCNT-SPCE,  were characterized by CV and  amperometry  in phosphate  buffer  solution  of  pH  7.50  for  the  H  ₂ O₂ determination.  Pd-MWCNT-SPCE  and  PdMWCNT/SPCEare convenient for the etermination of H 2O2 at working potentials from -0.50 to 0.50 V, and Pt-MWCNT-SPCE at investigated working potentials in the range from -0.80 to 0.70 V. These electrodes were then modified with glucose  oxidase (GOx) by drop coating a solution of GOxand Nafion ® on their surface, whereby the applied amount of biococktail was optimized. GOx/PdMWCNT-SPCE  showed  better  analytical  performance  for  glucose  determination  in  comparison with  GOx/Pd-MWCNT/SPCE.  The  optimal  working  potential  for  GOx/Pd-MWCNT- SPCE  was -0.40 V vs. SCE and  satisfactory linearity was obtained in the investigated glucose concentration range from 0.16 to 0.97 mmol L -1 (from 29.1 to 174  µg mL -1 ), hile the LOQ was 0.14 mmol L -1 (25 µg mL -1 ). The optimized method based on GOx/Pd-MWCNT-SPCE was successfully applied to the determination of glucose in multifloral honey sample.  The results are in a good agreement with those  obtained by commercially available equipment for determination of glucose. Optimal working potential  for  GOx/Pt-MWCNT-SPCE  was  -0.50  V  vs.  SCE,  and  the   satisfactory  linearity  was obtained in the investigated concentration range ofglucose from 65.8 to 260.6  µg mL -1 , with LOQ of 35  µg mL -1 . The optimized method based on GOx/Pt- MWCNT-SPCE was successfully applied for determination of glucose in white grape and glucose tablets (Traubenzucker-bonbons) samples, whereby  the  obtained  results  were  in  a  good  agreement  with  the  results  obtained  by  Accu-Chek device. Based on the results, the developed analytical methods are first of all simple, reliable and suitable  for  obtaining  fast  information  about  the  content  of  H ₂O₂ in  different  types  of  samples. Certainly the selection of a suitable working electrode, as well as the optimization of experimental conditions are key factors for the successful determination of H₂O₂ .

by Tang Chi Nang.
Thesis (M.Phil.)--Chinese University of Hong Kong, 1995.
Includes bibliographical references (leaves 104-[109]).
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Gaussian elimination --- p.2
Chapter 1.1.1 --- Numerical stability --- p.2
Chapter 1.2 --- Block Gaussian elimination --- p.3
Chapter 1.2.1 --- Numerical stability --- p.4
Chapter 1.3 --- Elimination graph --- p.4
Chapter 1.4 --- Elimination ordering --- p.5
Chapter 1.5 --- Computation and storage requirement --- p.6
Chapter 1.6 --- Outline of the thesis --- p.7
Chapter 2 --- Weighted graph elimination --- p.8
Chapter 2.1 --- Weighted elimination graph --- p.8
Chapter 2.2 --- Sparse Gaussian elimination --- p.9
Chapter 2.3 --- Computation and storage requirement --- p.12
Chapter 2.3.1 --- Computation requirement --- p.12
Chapter 2.3.2 --- Storage requirement --- p.14
Chapter 2.4 --- Elimination ordering --- p.15
Chapter 2.5 --- Repeated structure --- p.18
Chapter 3 --- Main theory --- p.21
Chapter 3.1 --- Motivation --- p.21
Chapter 3.2 --- Notations --- p.22
Chapter 3.2.1 --- Connectivity --- p.23
Chapter 3.2.2 --- Separator --- p.23
Chapter 3.2.3 --- Equivalence --- p.24
Chapter 3.3 --- Repetition separator --- p.25
Chapter 3.4 --- Repetition elimination process --- p.30
Chapter 3.5 --- Multiple Separators --- p.32
Chapter 3.6 --- Feasibility --- p.33
Chapter 3.6.1 --- Two-separator case --- p.34
Chapter 3.6.2 --- General case --- p.39
Chapter 3.6.3 --- Successive repetition elimination process (SREP) --- p.41
Chapter 3.7 --- Generalized repetition elimination process --- p.42
Chapter 3.7.1 --- Extra edges --- p.42
Chapter 3.7.2 --- Acyclic edges --- p.43
Chapter 3.7.3 --- Generalized repetition separator --- p.45
Chapter 4 --- Application in queueing analysis --- p.52
Chapter 4.1 --- Markov Chain Reduction Principle --- p.54
Chapter 4.1.1 --- Numerical stability --- p.57
Chapter 4.2 --- Multi-class MMPP/M/1/L queue --- p.57
Chapter 4.2.1 --- Single-class case (QBD case) --- p.58
Chapter 4.2.2 --- Preemptive LCFS case --- p.63
Chapter 4.2.3 --- Non-preemptive LCFS case --- p.70
Chapter 4.2.4 --- FCFS case --- p.72
Chapter 4.2.5 --- Extension to phase type service time --- p.77
Chapter 4.3 --- 2-class priority system --- p.77
Chapter 5 --- Choosing the right algorithm --- p.85
Chapter 5.1 --- MMPP/M/1/L system with bursty arrival --- p.86
Chapter 5.1.1 --- Algorithm Comparison --- p.89
Chapter 5.1.2 --- Numerical Examples --- p.90
Chapter 5.2 2 --- -class priority system --- p.90
Chapter 5.2.1 --- Algorithm Comparison --- p.95
Chapter 5.2.2 --- Numerical Examples --- p.95
Chapter 5.3 --- Conclusion --- p.95
Chapter 6 --- Conclusion --- p.98
Chapter 6.1 --- Further research --- p.99
Chapter A --- List of frequently-used notations --- p.101
Chapter A.l --- System of equations and Digraph --- p.101
Chapter A.2 --- General-purpose functions --- p.102
Chapter A.3 --- Single repetition separator --- p.102
Chapter A.4 --- Sequence of repetition separators --- p.103
Chapter A.5 --- Compatibility --- p.103
Bibliography --- p.104

Cheung, Yat Ming.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2010.
Includes bibliographical references (leaves 75-78).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.6
Chapter 2 --- Symplectic Geometry and Special Lagrangian Graphs in Cn --- p.10
Chapter 2.1 --- Symplectic and Lagrangian Geometry of Cn --- p.10
Chapter 2.2 --- Calibrated and Spccial Lagrangian Geometries in Cn --- p.13
Chapter 2.3 --- Special Lagrangian Differential Equation --- p.16
Chapter 3 --- Contact Geometry in S2n-1 --- p.20
Chapter 3.1 --- Contact and Legendrian Geometries in S2n-1 --- p.20
Chapter 3.2 --- Special Lagrangian Cone in R2n --- p.24
Chapter 3.3 --- The Second Fundamental Form of Lagrangian Cone in E2n --- p.26
Chapter 4 --- Geometry of Grassmannians --- p.29
Chapter 4.1 --- Locally Symmetric Space --- p.29
Chapter 4.2 --- "The Grassmann manifold G(n, m)" --- p.33
Chapter 4.3 --- "Leichtweiss' Formula for Curvature Tensor in G(n, m)" --- p.36
Chapter 4.4 --- "Normal Neighbourhoods of a Point in G(n, m)" --- p.39
Chapter 4.5 --- Some Remarks on Lagrangian Grassmannians --- p.49
Chapter 5 --- Harmonic Maps between Riemannian Manifolds --- p.51
Chapter 5.1 --- Energy Functional and Tension Field --- p.52
Chapter 5.2 --- Harmonic Map and Euler-Lagrange Equation --- p.56
Chapter 5.3 --- The Gauss Map and its Tension Field --- p.59
Chapter 5.4 --- Simple Riemannian Manifolds and A Liouville-Type Result of Har- monic Maps --- p.63
Chapter 6 --- Bernstein-Type Results for Special Lagrangian Graphs --- p.65
Chapter 6.1 --- Convexity and Bounded Slope Assumption --- p.65
Chapter 6.2 --- Spherical Bernstein-Type Result --- p.68
Chapter 6.3 --- Bernstein-Type Result with only Bounded Slope --- p.72
Bibliography --- p.75

We consider complete asymptotically flat Riemannian manifolds that are the graphs of smooth functions over $\mathbb R^n$. By recognizing the scalar curvature of such manifolds as a divergence, we express the ADM mass as an integral of the product of the scalar curvature and a nonnegative potential function, thus proving the Riemannian positive mass theorem in this case. If the graph has convex horizons, we also prove the Riemannian Penrose inequality by giving a lower bound to the boundary integrals using the Aleksandrov-Fenchel inequality. We also prove the ZAS inequality for graphs in Minkowski space. Furthermore, we define a new quasi-local mass functional and show that it satisfies certain desirable properties.

Dissertation

RNA-Seq is an increasingly popular approach to transcriptome profiling that uses the capabilities of next generation sequencing technologies and provides better measurement of levels of transcripts and their isoforms. In this thesis, we apply RNA-Seq protocol and transcriptome quantification to estimate gene expression and pathway activity levels. We present a novel method, called IsoDE, for differential gene expression analysis based on bootstrapping. In the first version of IsoDE, we compared the tool against four existing methods: Fisher's exact test, GFOLD, edgeR and Cuffdiff on RNA-Seq datasets generated using three different sequencing technologies, both with and without replicates. We also introduce the second version of IsoDE which runs 10 times faster than the first implementation due to some in-memory processing applied to the underlying gene expression frequencies estimation tool and we also perform more optimization on the analysis. The second part of this thesis presents a set of tools to differentially analyze metabolic pathways from RNA-Seq data. Metabolic pathways are series of chemical reactions occurring within a cell. We focus on two main problems in metabolic pathways differential analysis, namely, differential analysis of their inferred activity level and of their estimated abundance. We validate our approaches through differential expression analysis at the transcripts and genes levels and also through real-time quantitative PCR experiments. In part Four, we present the different packages created or updated in the course of this study. We conclude with our future work plans for further improving IsoDE 2.0.

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.

We study a system of differential-algebraic equations, describing motions of a mass-spring-dashpot oscillator by three different forms of implicit constitu- tive relations. For some problems with fully implicit but linear constitutive laws for combined force, we find conditions for solution stability. Assuming monotone relationship between the displacement, velocity and the respective forces, we prove global existence of the solutions. For a linear spring and a dashpot with maximal monotone relationship between the damping force and the velocity, we prove the global existence and uniqueness result. We also solve this problem numerically for Coulomb-like damping term.

In the first part we prove a general existence theory for constrained minimization problems for functionals defined on function spaces on metric measure spaces (M, d, μ). We apply this theory to functionals defined on metric graphs G. We show how the existence of solutions can be obtained via decomposition methods using spectral properties of the operator A associated with the form a(・, ・) and discuss the spectral quantities involved. Concrete examples considered include higher order NLS functionals and metric graphs with infinite edge set and magnetic potentials. This generalizes results obtained by Adami, Serra and Tilli [JFA 271 (2016), 201- 223], and Cacciapuoti, Finco and Noja [Nonlinearity 30 (2017), 3271-3303], among others. In the second part we consider spectral minimal partitions of compact metric graphs. We motivate their study through Nehari ground state problems and certain penalized systems. We relate a class of minimal partitions to eigenvalues of the Laplacian and show sharp lower and upper estimates for the associated spectral minimal energies LDk ,∞ and LNk ,∞, estimates between these energies and eigenvalues of the Laplacian, which in some cases result in better estimates than the ones previously obtained in Berkolaiko et al [J. Phys. A 50 (2017), 365201] In the third partwe establish metric graph counterparts of Pleijel’s theorem on the asymptotics of the number of nodal domains νn of the n-th eigenfunction(s) of a broad class of operators on compact metric graphs. Among other things, these results characterize the accumulation points of the sequence ( νn n )n∈N, which are shown always to form a finite subset of (0, 1]. In the final part we introduce a numerical method for calculating the eigenvalues of the standard Laplacian based on a discrete graph approximation and von Below’s theorem.

This thesis concerns chosen problems of privacy preserving data aggregation. It is based on differential privacy, which is a mathematically rigorous privacy definition resilient to post-processing. Differential privacy is connected with randomization of the result. The goal is to achieve both sufficient privacy and accuracy. We are interested in practical scenarios, so we consider aggregation in distributed systems with unreliable nodes and untrusted aggregator. First, we analyse current state-of-the-art solution and show that despite good asymptotical guarantees for the accuracy, in many practical scenarios the errors are unacceptably high. We present our own fault tolerant privacy preserving data aggregation protocol which utilizes limited local communication between nodes. We show that our protocol provides provable level of privacy and far better accuracy even when facing massive failures of nodes. Next, to make our results useful in wider scenarios, we show how to construct local groups of trust in real-life networks. We consider a distributed system that consists of nodes which need to constitute a huge, connected group in an efficient way, using simple operations and without knowledge of global network topology. We propose and investigate local strategies for constructing large groups of users with low communication and computation overhead. Moreover, we prove some properties of real-life networks while formally assuming that they are generated as a preferential attachment process. Finally, we took a different approach and focused instead on the privacy definition itself. We look from different perspective at an, already known, relaxation of differential privacy called noiseless privacy. It utilizes the randomness in the data, which can either come inherently from the data itself, or model the uncertainty of the Adversary. In contrast to previous work, which focused on asymptotic results, independent data and specific distributions, we give nonasymptotic privacy guarantees for any distribution and a wide class of dependencies. We show a way to combine differential privacy with noiseless privacy and present detailed results which can be easily applied in real-life scenarios of data aggregation.
Przedmiotem tej rozprawy s ˛a wybrane problemy agregacji danych z zachowaniem prywatnosci. Rozprawa jest oparta o ´ prywatnos´c ró ´ znicow ˛a ˙ (differential privacy), która, w odróznieniu od wcze ˙ sniejszych definicji prywatno ´ sci, jest oparta na for- ´ malizmie matematycznym. Prywatnos´c ró ´ znicowa wi ˛a ˙ ze si˛e z odpowiedni ˛a ran- ˙ domizacj ˛a wyniku. Interesuj ˛a nas praktyczne scenariusze, wi˛ec rozwazamy agre- ˙ gacje w rozproszonych systemach z zawodnymi w˛ezłami i niezaufanym agregatorem. Zaczniemy od przeanalizowania aktualnego rozwi ˛azania problemu i wskazania, ze pomimo dobrych asymptotycznych gwarancji dokładno ˙ sci, w wielu prakty- ´ cznych scenariuszach bł˛edy wynikaj ˛ace z dodanych szumów s ˛a nieakceptowalnie duze. Nast˛epnie proponujemy skonstruowany przez nas protokół, który wyko- ˙ rzystuje ograniczon ˛a, lokaln ˛a komunikacj˛e pomi˛edzy w˛ezłami. Pokazujemy, ze˙ nasz protokół zapewnia dowodliw ˛a prywatnos´c oraz jest znacznie dokładniejszy, ´ nawet gdy wiele w˛ezłów jest zawodnych. Nast˛epnie, aby nasze wyniki były uzyteczne w szerszej klasie scenariuszy, pokazu- ˙ jemy jak skonstruowac lokalne grupy ufaj ˛acych sobie w˛ezłów w realistycznych ´ sieciach. Rozwazamy rozproszony system składaj ˛acy si˛e z w˛ezłów, które musz ˛a ˙ stworzyc du ´ z ˛a, spójn ˛a grup˛e w sposób efektywny i bez znajomo ˙ sci topologii sieci. ´ Proponujemy i badamy lokalne strategie konstruowania duzych grup z małym ˙ narzutem komunikacyjnym i obliczeniowym. Ponadto udowadniamy niektóre własnosci prawdziwych sieci przy zało ´ zeniu, ˙ ze pochodz ˛a z modelu ˙ preferential attachment. Na koniec koncentrujemy si˛e na samej definicji prywatnosci. Rozwa ´ zamy, znane ˙ wczesniej, osłabienie prywatno ´ sci ró ´ znicowej, ˙ noiseless privacy, wykorzystuj ˛ace ograniczon ˛a losowos´c danych. Mo ´ ze ona równie ˙ z modelowa ˙ c niepewno ´ s´c adw- ´ ersarza. W odróznieniu od istniej ˛acych wyników, które skupiały si˛e na wynikach ˙ asymptotycznych, niezaleznych danych i konkretnych rozkładach danych, przed- ˙ stawiamy nieasymptotyczne gwarancje prywatnosci dla dowolnych rozkładów i ´ szerokiej klasy zalezno ˙ sci. Pokazujemy jak poł ˛aczy ´ c prywatno ´ s´c ró ´ znicow ˛a z ˙ noiseless privacy oraz przedstawiamy precyzyjne wyniki, które mog ˛a byc łatwo ´ wykorzystane w praktycznych zastosowaniach agregacji danych.

Nous présentons dans cette thèse des théorèmes de point fixe pour des contractions multivoques définies sur des espaces métriques, et, sur des espaces de jauges munis d’un graphe. Nous illustrons également les applications de ces résultats à des inclusions intégrales et à la théorie des fractales. Cette thèse est composée de quatre articles qui sont présentés dans quatre chapitres. Dans le chapitre 1, nous établissons des résultats de point fixe pour des fonctions multivoques, appelées G-contractions faibles. Celles-ci envoient des points connexes dans des points connexes et contractent la longueur des chemins. Les ensembles de points fixes sont étudiés. La propriété d’invariance homotopique d’existence d’un point fixe est également établie pour une famille de Gcontractions multivoques faibles. Dans le chapitre 2, nous établissons l’existence de solutions pour des systèmes d’inclusions intégrales de Hammerstein sous des conditions de type de monotonie mixte. L’existence de solutions pour des systèmes d’inclusions différentielles avec conditions initiales ou conditions aux limites périodiques est également obtenue. Nos résultats s’appuient sur nos théorèmes de point fixe pour des G-contractions multivoques faibles établis au chapitre 1. Dans le chapitre 3, nous appliquons ces mêmes résultats de point fixe aux systèmes de fonctions itérées assujettis à un graphe orienté. Plus précisément, nous construisons un espace métrique muni d’un graphe G et une G-contraction appropriés. En utilisant les points fixes de cette G-contraction, nous obtenons plus d’information sur les attracteurs de ces systèmes de fonctions itérées. Dans le chapitre 4, nous considérons des contractions multivoques définies sur un espace de jauges muni d’un graphe. Nous prouvons un résultat de point fixe pour des fonctions multivoques qui envoient des points connexes dans des points connexes et qui satisfont une condition de contraction généralisée. Ensuite, nous étudions des systèmes infinis de fonctions itérées assujettis à un graphe orienté (H-IIFS). Nous donnons des conditions assurant l’existence d’un attracteur unique à un H-IIFS. Enfin, nous appliquons notre résultat de point fixe pour des contractions multivoques définies sur un espace de jauges muni d’un graphe pour obtenir plus d’information sur l’attracteur d’un H-IIFS. Plus précisément, nous construisons un espace de jauges muni d’un graphe G et une G-contraction appropriés tels que ses points fixes sont des sous-attracteurs du H-IIFS.
In this thesis, we present fixed point theorems for multivalued contractions defined on metric spaces, and, on gauge spaces endowed with directed graphs. We also illustrate the applications of these results to integral inclusions and to the theory of fractals. chapters. In Chapter 1, we establish fixed point results for the maps, called multivalued weak G-contractions, which send connected points to connected points and contract the length of paths. The fixed point sets are studied. The homotopical invariance property of having a fixed point is also established for a family of weak G-contractions. In Chapter 2, we establish the existence of solutions of systems of Hammerstein integral inclusions under mixed monotonicity type conditions. Existence of solutions to systems of differential inclusions with initial value condition or periodic boundary value condition are also obtained. Our results rely on our fixed point theorems for multivalued weak G-contractions established in Chapter 1. In Chapter 3, those fixed point results for multivalued G-contractions are applied to graph-directed iterated function systems. More precisely, we construct a suitable metric space endowed with a graph G and an appropriate G-contraction. Using the fixed points of this G-contraction, we obtain more information on the attractors of graph-directed iterated function systems. In Chapter 4, we consider multivalued maps defined on a complete gauge space endowed with a directed graph. We establish a fixed point result for maps which send connected points into connected points and satisfy a generalized contraction condition. Then, we study infinite graph-directed iterated function systems (H-IIFS). We give conditions insuring the existence of a unique attractor to an H-IIFS. Finally, we apply our fixed point result for multivalued contractions on gauge spaces endowed with a graph to obtain more information on the attractor of an H-IIFS. More precisely, we construct a suitable gauge space endowed with a graph G and a suitable multivalued G-contraction such that its fixed points are sub-attractors of the H-IIFS.

This thesis deals with cohomologies on the symplectic quotient of a Frölicher space which is locally diffeomorphic to a Euclidean Frölicher subspace of Rn of constant dimension equal to n. The symplectic reduction under consideration in this thesis is an extension of the Marsden-Weinstein quotient (also called, the reduced space) well-known from the finite-dimensional smooth manifold case. That is, starting with a proper and free action of a Frölicher-Lie-group on a locally Euclidean Frölicher space of finite constant dimension, we study the smooth structure and the topology induced on a small subspace of the orbit space. It is on this topological space that we will construct selected cohomologies such as : sheaf cohomology, Alexander-Spanier cohomology, singular cohomology, ~Cech cohomology and de Rham cohomology. Some natural questions that will be investigated are for instance: the impact of the symplectic structure on these di erent cohomologies; the cohomology that will give a good description of the topology on the objects of category of Frölicher spaces; the extension of the de Rham cohomology theorem in order to establish an isomorphism between the five cohomologies. Beside the algebraic, topological and geometric study of these new objects, the thesis contains a modern formalism of Hamiltonian mechanics on the reduced space under symplectic and Poisson structures.
Mathematical Sciences
D. Phil. (Mathematics)