As social networks become more prevalent, there is significant interest in studying these network data, the focus often being on detecting anomalous events. This area of research is referred to as social network surveillance or social network change detection. While there are a variety of proposed methods suitable for different monitoring situations, two important issues have yet to be completely addressed in network surveillance literature. First, performance assessments using simulated data to evaluate the statistical performance of a particular method. Second, the study of aggregated data in social network surveillance. The research presented tackle these issues in two parts, evaluation of a popular anomaly detection method and investigation of the effects of different aggregation levels on network anomaly detection. / Ph. D.

LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 59 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza- Ceará, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T18:53:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T19:18:47Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-06-13T19:18:47Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom. / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set.

In this thesis we consider extensions and generalizations of some classical problems in Combinatorial Geometry. Our work is an offshoot of four classical problems in Combinatorial Geometry. A fundamental assumption in these problems is that the underlying point set is R2. Two fundamental themes entwining the problems considered in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since. Avis et al. in 2001 posed the following question which we call the n-interior point problem: Is there a finite integer g(n) for every n, such that, every point set P with g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset which is a convex polygon that contains exactly n interior points. They showed that g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers. We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed the following fundamental question which can be considered as a generalised version of Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known. Inspired by the original question of Danzer and Gr¨unbaum we consider their question in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting. In the third part of this thesis, we broadly look at hitting and covering questions with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively. These problems has been well studied in the case when P = R2. We systematically look at the case when P is finite, showing bounds for intervals, halfspaces, orthants, unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2. Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express the bound on the size of the set Q in terms of ǫ. Let G be a uniform √n × √n grid. It is an intriguing question as to whether we get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.

Le sujet principal de ce mémoire est l'étude de la distribution asymptotique de la fonction f_m qui compte le nombre de diviseurs premiers distincts parmi les nombres premiers $p_1,...,p_m$. Au premier chapitre, nous présentons les sept résultats qui seront démontrés au chapitre 4. Parmi ceux-ci figurent l'analogue du théorème d'Erdos-Kac et un résultat sur les grandes déviations. Au second chapitre, nous définissons les espaces de probabilités qui serviront à calculer les probabilités asymptotiques des événements considérés, et éventuellement à calculer les densités qui leur correspondent. Le troisième chapitre est la partie centrale du mémoire. On y définit la promenade aléatoire qui, une fois normalisée, convergera vers le mouvement brownien. De là, découleront les résultats qui formeront la base des démonstrations de ceux chapitre 1. / The main topic of this masters thesis is the study of the asymptotic distribution of the fonction f_m which counts the number of distinct prime divisors among the first $m$ prime numbers, i.e. $p_1,...,p_m$. The first chapter provides the seven main results which will later on be proved in chapter 4. Among these we find the analogue of the Erdos-Kac central limit theorem and a result on large deviations. In the following chapter, we define several probability spaces on which we will calculate asymptotic probabilities of specific events. These will become necessary for calculating their corresponding densities. The third chapter is the main part of this masters thesis. In it, we introduce a random walk which, when suitably normalized, will converge to the Brownian motion. We will then obtain results which will form the basis of the proofs of those of chapiter 1.

Le sujet principal de ce mémoire est l'étude de la distribution asymptotique de la fonction f_m qui compte le nombre de diviseurs premiers distincts parmi les nombres premiers $p_1,...,p_m$. Au premier chapitre, nous présentons les sept résultats qui seront démontrés au chapitre 4. Parmi ceux-ci figurent l'analogue du théorème d'Erdos-Kac et un résultat sur les grandes déviations. Au second chapitre, nous définissons les espaces de probabilités qui serviront à calculer les probabilités asymptotiques des événements considérés, et éventuellement à calculer les densités qui leur correspondent. Le troisième chapitre est la partie centrale du mémoire. On y définit la promenade aléatoire qui, une fois normalisée, convergera vers le mouvement brownien. De là, découleront les résultats qui formeront la base des démonstrations de ceux chapitre 1. / The main topic of this masters thesis is the study of the asymptotic distribution of the fonction f_m which counts the number of distinct prime divisors among the first $m$ prime numbers, i.e. $p_1,...,p_m$. The first chapter provides the seven main results which will later on be proved in chapter 4. Among these we find the analogue of the Erdos-Kac central limit theorem and a result on large deviations. In the following chapter, we define several probability spaces on which we will calculate asymptotic probabilities of specific events. These will become necessary for calculating their corresponding densities. The third chapter is the main part of this masters thesis. In it, we introduce a random walk which, when suitably normalized, will converge to the Brownian motion. We will then obtain results which will form the basis of the proofs of those of chapiter 1.

<p dir="ltr">Since graphs are natural representations for encoding relational data, the problem of graph matching is an emerging task and has attracted increasing attention, which could potentially impact various domains such as social network de-anonymization and computer vision. Our main interest is designing polynomial-time algorithms for seeded graph matching problems where a subset of pre-matched vertex-pairs (seeds) is revealed. </p><p dir="ltr">However, the existing work does not fully investigate the pivotal role of seeds and falls short of making the most use of the seeds. Notably, the majority of existing hand-crafted algorithms only focus on using ``witnesses'' in the 1-hop neighborhood. Although some advanced algorithms are proposed to use multi-hop witnesses, their theoretical analysis applies only to \ER random graphs and requires seeds to be all correct, which often do not hold in real applications. Furthermore, a parallel line of research, Graph Neural Network (GNN) approaches, typically employs a semi-supervised approach, which requires a large number of seeds and lacks the capacity to distill knowledge transferable to unseen graphs.</p><p dir="ltr">In my dissertation, I have taken two approaches to address these limitations. In the first approach, we study to design hand-crafted algorithms that can properly use multi-hop witnesses to match graphs. We first study graph matching using multi-hop neighborhoods when partially-correct seeds are provided. Specifically, consider two correlated graphs whose edges are sampled independently from a parent \ER graph $\mathcal{G}(n,p)$. A mapping between the vertices of the two graphs is provided as seeds, of which an unknown fraction is correct. We first analyze a simple algorithm that matches vertices based on the number of common seeds in the $1$-hop neighborhoods, and then further propose a new algorithm that uses seeds in the $D$-hop neighborhoods. We establish non-asymptotic performance guarantees of perfect matching for both $1$-hop and $2$-hop algorithms, showing that our new $2$-hop algorithm requires substantially fewer correct seeds than the $1$-hop algorithm when graphs are sparse. Moreover, by combining our new performance guarantees for the $1$-hop and $2$-hop algorithms, we attain the best-known results (in terms of the required fraction of correct seeds) across the entire range of graph sparsity and significantly improve the previous results. We then study the role of multi-hop neighborhoods in matching power-law graphs. Assume that two edge-correlated graphs are independently edge-sampled from a common parent graph with a power-law degree distribution. A set of correctly matched vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to use the seeds to recover the remaining latent vertex correspondence between the two graphs. Departing from the existing approaches that focus on the use of high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods. Our result achieves an exponential reduction in the seed size requirement compared to the best previously known results.</p><p dir="ltr">In the second approach, we study GNNs for seeded graph matching. We propose a new supervised approach that can learn from a training set how to match unseen graphs with only a few seeds. Our SeedGNN architecture incorporates several novel designs, inspired by our theoretical studies of seeded graph matching: 1) it can learn to compute and use witness-like information from different hops, in a way that can be generalized to graphs of different sizes; 2) it can use easily-matched node-pairs as new seeds to improve the matching in subsequent layers. We evaluate SeedGNN on synthetic and real-world graphs and demonstrate significant performance improvements over both non-learning and learning algorithms in the existing literature. Furthermore, our experiments confirm that the knowledge learned by SeedGNN from training graphs can be generalized to test graphs of different sizes and categories.</p>

Social networks play an important role in disseminating a piece of information in a population. Companies advertising a newly launched product, movie promotion, political campaigns, social awareness campaigns by governments, charity campaigns by NGOs and crowd funding campaigns by entrepreneurs are a few examples where an entity is interested in disseminating a piece of information in a target population, possibly under resource constraints. In this thesis we model information diffusion in a population using various epidemic models and study optimal campaigning strategies to maximize the reach of information. In the different problems considered in this thesis, information epidemics are modeled as the Susceptible-Infected, Susceptible-Infected-Susceptible, Susceptible-Infected-Recovered and Maki Thompson epidemic processes; however, we modify the models to incorporate the intervention made by the campaigner to enhance information propagation. Direct recruitment of individuals as spreaders and providing word-of-mouth incentives to the spreaders are considered as two intervention strategies (controls) to enhance the speed of information propagation. These controls can be implemented by placing advertisements in the mass media, announcing referral/cash back rewards for introducing friends to a product or service being advertised etc. In the different problems considered in this thesis, social contacts are modeled with varying levels of complexity---population is homogeneously mixed or follows heterogeneous mixing. The solutions to the problems which consider homogeneous mixing of individuals identify the most important periods in the campaign duration which should be allocated more resources to maximize the reach of the message, depending on the system parameters of the epidemic model (e.g., epidemics with high and low virulence). When a heterogeneous model is considered, apart from this, the solution identifies the important classes of individuals which should be allocated more resources depending upon the network considered (e.g. Erdos-Renyi, scale-free) and model parameters. These classes may be carved out based on various centrality measures in the network. If multiple strategies are available for campaigning, the solution also identifies the relative importance of the strategies depending on the network type. We study variants of the optimal campaigning problem where we optimize different objective functions. For some of the formulated problems, we discuss the existence and uniqueness of the solution. Sometimes our formulations call for novel techniques to prove the existence of a solution.

Soit q ⩾ 2 une puissance première fixe. L’objectif principal de cette thèse est d’étudier le comportement asymptotique de la fonction arithmétique Π_q(n,k) comptant le nombre de polynômes moniques de degré n et ayant exactement k facteurs irréductibles (avec multiplicité) sur le corps fini F_q. Warlimont et Car ont montré que l’objet Π_q(n,k) est approximativement distribué de Poisson lorsque 1 ⩽ k ⩽ A log n pour une constante A > 0. Plus tard, Hwang a étudié la fonction Π_q(n,k) pour la gamme complète 1 ⩽ k ⩽ n. Nous allons d’abord démontrer une formule asymptotique pour Π_q(n,k) en utilisant une technique analytique classique développée par Sathe et Selberg. Nous reproduirons ensuite une version simplifiée du résultat de Hwang en utilisant la formule de Sathe-Selberg dans le champ des fonctions. Nous comparons également nos résultats avec ceux analogues existants dans le cas des entiers, où l’on étudie tous les nombres naturels jusqu’à x avec exactement k facteurs premiers. En particulier, nous montrons que le nombre de polynômes moniques croît à un taux étonnamment plus élevé lorsque k est un peu plus grand que logn que ce que l’on pourrait supposer en examinant le cas des entiers. Pour présenter le travail ci-dessus, nous commençons d’abord par la théorie analytique des nombres de base dans le contexte des polynômes. Nous introduisons ensuite les fonctions arithmétiques clés qui jouent un rôle majeur dans notre thèse et discutons brièvement des résultats bien connus concernant leur distribution d’un point de vue probabiliste. Enfin, pour comprendre les résultats clés, nous donnons une discussion assez détaillée sur l’analogue de champ de fonction de la formule de Sathe-Selberg, un outil récemment développé par Porrit et utilisons ensuite cet outil pour prouver les résultats revendiqués. / Let q ⩾ 2 be a fixed prime power. The main objective of this thesis is to study the asymptotic behaviour of the arithmetic function Π_q(n,k) counting the number of monic polynomials that are of degree n and have exactly k irreducible factors (with multiplicity) over the finite field F_q. Warlimont and Car showed that the object Π_q(n,k) is approximately Poisson distributed when 1 ⩽ k ⩽ A log n for some constant A > 0. Later Hwang studied the function Π_q(n,k) for the full range 1 ⩽ k ⩽ n. We will first prove an asymptotic formula for Π_q(n,k) using a classical analytic technique developed by Sathe and Selberg. We will then reproduce a simplified version of Hwang’s result using the Sathe-Selberg formula in the function field. We also compare our results with the analogous existing ones in the integer case, where one studies all the natural numbers up to x with exactly k prime factors. In particular, we show that the number of monic polynomials grows at a surprisingly higher rate when k is a little larger than logn than what one would speculate from looking at the integer case. To present the above work, we first start with basic analytic number theory in the context of polynomials. We then introduce the key arithmetic functions that play a major role in our thesis and briefly discuss well-known results concerning their distribution from a probabilistic point of view. Finally, to understand the key results, we give a fairly detailed discussion on the function field analogue of the Sathe-Selberg formula, a tool recently developed by Porrit and subsequently use this tool to prove the claimed results.