<p>We survey the problem of covering and partitioning a bipartite graph using vertex-disjoint unions of bicliques. The concept of a vertex-disjoint union of bicliques has been given many names in computer science: it has been termed a blocky matrix in communication complexity,</p> <p>a fat matching in circuit complexity, a bipartite P4-free graph in graph theory, a simple graph in cryptography, and a bicluster in bioinformatics. We aim to unify all of these perspectives, compiling what is known and unknown about the problem, including discussion on upper and lower bounding techniques for the problem, bounds for specific families of graphs, and</p> <p>the hardness of computation of the problem. Along the way, we present a new explicit graph for which the covering and partitioning numbers are different.</p>

Lattices are an easy and clean class of periodic arrangements that are not only discrete but associated with algebraic structures. We will specifically discuss applying lattices theory to computing the area of polygons in the plane and some optimization problems. This thesis will details information about Pick's Theorem and the higher-dimensional cases of Ehrhart Theory. Closely related to Pick's Theorem and Ehrhart Theory is the Frobenius Problem and Integer Knapsack Problem. Both of these problems have higher-dimension applications, where the difficulties are similar to those of Pick's Theorem and Ehrhart Theory. We will directly relate these problems to optimization problems and operations research.

This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random Fields. We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraint in terms of certain algebraic properties, and extend this result by showing yet another connection between the expressive power of valued constraints and linear programming. We prove a decidability result for fractional clones. We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We present a full classification of various classes of constraints with respect to this problem. We study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

We study admissible transformations and solve group classification problems for various classes of linear and nonlinear Schrödinger equations with an arbitrary number n of space variables. The aim of the thesis is twofold. The first is the construction of the new theory of uniform seminormalized classes of differential equations and its application to solving group classification problems for these classes. Point transformations connecting two equations (source and target) from the class under study may have special properties of semi-normalization. This makes the group classification of that class using the algebraic method more involved. To extend this method we introduce the new notion of uniformly semi-normalized classes. Various types of uniform semi-normalization are studied: with respect to the corresponding equivalence group, with respect to a proper subgroup of the equivalence group as well as the corresponding types of weak uniform semi-normalization. An important kind of uniform semi-normalization is given by classes of homogeneous linear differential equations, which we call uniform semi-normalization with respect to linear superposition of solutions. The class of linear Schrödinger equations with complex potentials is of this type and its group classification can be effectively carried out within the framework of the uniform semi-normalization. Computing the equivalence groupoid and the equivalence group of this class, we show that it is uniformly seminormalized with respect to linear superposition of solutions. This allow us to apply the version of the algebraic method for uniformly semi-normalized classes and to reduce the group classification of this class to the classification of appropriate subalgebras of its equivalence algebra. To single out the classification cases, integers that are invariant under equivalence transformations are introduced. The complete group classification of linear Schrödinger equations is carried out for the cases n = 1 and n = 2. The second aim is to study group classification problem for classes of generalized nonlinear Schrödinger equations which are not uniformly semi-normalized. We find their equivalence groupoids and their equivalence groups and then conclude whether these classes are normalized or not. The most appealing classes are the class of nonlinear Schrödinger equations with potentials and modular nonlinearities and the class of generalized Schrödinger equations with complex-valued and, in general, coefficients of Laplacian term. Both these classes are not normalized. The first is partitioned into an infinite number of disjoint normalized subclasses of three kinds: logarithmic nonlinearity, power nonlinearity and general modular nonlinearity. The properties of the Lie invariance algebras of equations from each subclass are studied for arbitrary space dimension n, and the complete group classification is carried out for each subclass in dimension (1+2). The second class is successively reduced into subclasses until we reach the subclass of (1+1)-dimensional linear Schrödinger equations with variable mass, which also turns out to be non-normalized. We prove that this class is mapped by a family of point transformations to the class of (1+1)-dimensional linear Schrödinger equations with unique constant mass.

This thesis examines the domination number of the semi-strong product of two graphs G and H where both G and H are simple and connected graphs. The product has an edge set that is the union of the edge set of the direct product of G and H together with the cardinality of V(H), copies of G. Unlike the other more common products (Cartesian, direct and strong), the semi-strong product is neither commutative nor associative. The semi-strong product is not supermultiplicative, so it does not satisfy a Vizing like conjecture. It is also not submultiplicative so it shares these two properties with the direct product. After giving the basic definitions related with graphs, domination in graphs and basic properties of the semi-strong product, this paper includes a general upper bound for the domination of the semi-strong product of any two graphs G and H as less than or equal to twice the domination numbers of each graph individually. Similar general results for the semi-strong product perfect-paired domination numbers of any two graphs G and H, as well as semi-strong products of some specific types of cycle graphs are also addressed.

Today, better numerical approximations are required for multi-dimensional SDEs to improve on the poor performance of the standard Monte Carlo integration. With this aim in mind, the material in the thesis is divided into two main categories, stochastic calculus and mathematical finance. In the former, we introduce a new scheme or discrete time approximation based on an idea of Paul Malliavin where, for some conditions, a better strong convergence order is obtained than the standard Milstein scheme without the expensive simulation of the Lévy Area. We demonstrate when the conditions of the 2−Dimensional problem permit this and give an exact solution for the orthogonal transformation (θ Scheme or Orthogonal Milstein Scheme). Our applications are focused on continuous time diffusion models for the volatility and variance with their discrete time approximations (ARV). Two theorems that measure with confidence the order of strong and weak convergence of schemes without an exact solution or expectation of the system are formally proved and tested with numerical examples. In addition, some methods for simulating the double integrals or Lévy Area in the Milstein approximation are introduced. For mathematical finance, we review evidence of non-constant volatility and consider the implications for option pricing using stochastic volatility models. A general stochastic volatility model that represents most of the stochastic volatility models that are outlined in the literature is proposed. This was necessary in order to both study and understand the option price properties. The analytic closed-form solution for a European/Digital option for both the Square Root Model and the 3/2 Model are given. We present the Multilevel Monte Carlo path simulation method which is a powerful tool for pricing exotic options. An improved/updated version of the ML-MC algorithm using multi-schemes and a non-zero starting level is introduced. To link the contents of the thesis, we present a wide variety of pricing exotic option examples where considerable computational savings are demonstrated using the new θ Scheme and the improved Multischeme Multilevel Monte Carlo method (MSL-MC). The computational cost to achieve an accuracy of O(e) is reduced from O(e−3) to O(e−2) for some applications.

[pt] Os desafios de estudar formas levaram matemáticos a criar abstrações, em particular através da geometria diferencial. Porém, formas simples como cubos não se adequam a ferramentas diferenciáveis. Este trabalho é uma tentativa de usar avanços recentes da análise, no caso a teoria das distribuições, para estender quantidades diferenciáveis a objetos singulares. Como as distribuições generalizam as funções e permitem derivações infinitas, substituição das parametrizações de subvariedades clássicas por distribuições poderia naturalmente generalizar as subvariedades suaves. Isso nos leva a definir D-imersões. Esse trabalho demonstra que essa formulação, de fato, generaliza as imersões suaves. Extensões para outras classes de subvariedades são discutidas através de exemplos e casos particulares. / [en] The challenge of studying shapes has led mathematicians to create powerful abstract concepts, in particular through Differential Geometry. However, differential tools do not apply to simple shapes like cubes. This work is an attempt to use modern advances of the Analysis, namely Distribution Theory, to extend differential quantities to singular objects. Distributions generalize functions, while allowing infinite differentiation. The substitution of classical immersions, which usually serve as submanifold parameterizations, by distributions might thus naturally generalize smooth immersion. This leads to the concept of D-immersion. This work proves that this formulation actually generalizes smooth immersions. Extensions to non-smooth of immersions are discussed through examples and specific cases.

In this thesis, we discuss important results for the numerical range of general square matrices. Especially, we examine analytically the numerical range of complex-valued $2 \times 2$ matrices. Also, we investigate and discuss the Gershgorin region of general square matrices. Lastly, we examine numerically the numerical range and Gershgorin regions for different types of square matrices, both contain the spectrum of the matrix, and compare these regions, using the calculation software Maple.

La recherche que nous avons menée s'inscrit dans les projets de l'équipe de recherche Maths à Modeler. En particulier dans celui portant sur les situations de recherche en classe (Grenier et Payan, 2002 ; Ouvrier-Buffet, 2003 ; Godot, 2005 ; Cartier, 2008). Cette étude est centrée sur la démarche de recherche en mathématiques et plus particulièrement sur le rôle de l'expérimental. Un des postulats fondateur de notre recherche est que savoir faire des mathématiques, c'est savoir résoudre partiellement des problèmes de recherche, la résolution de tels problèmes nécessitant de passer par des phases expérimentales. Notre problématique porte donc sur la transmission aux élèves du savoir-faire « démarche expérimentale en mathématiques » et sur le rôle que celui-ci joue dans la résolution de problèmes de recherche. Considérant que ce savoir-faire ne peut s'apprendre qu'à travers sa pratique en situation de résolution de problèmes, l'objectif de notre recherche a été la détermination de conditions épistémologiques et didactiques favorisant la mise en pratique de la « démarche expérimentale ». En plus de la construction d'un modèle de situation pour la « démarche expérimentale », nous avons construit, analysé et expérimenté des situations se référant à ce modèle. Pour mener à bien notre étude, nous avons utilisé le modèle de situation de recherche pour la classe (Grenier et Payan, 2002 ; Godot, 2005), ainsi que des éléments de la théorie des situtions didactiques de Brousseau (1998), en particulier validation a-didactique, contrat didactique et milieu. Nous avons aussi défini un modèle de « démarche expérimentale en mathématiques » qui a servi de référant à notre recherche. Après avoir observé que la « démarche expérimentale en mathématiques », telle que nous l'entendons, n'est pas proposée par l'institution scolaire, les expérimentations et les analyses, que nous avons menées, ont montré que, dans une certaine mesure, il est possible de la faire pratiquer à des élèves. De plus, cette pratique a permis aux élèves de progresser dans la résolution grâce à un enrichissement des conceptions qu'ils portaient sur le problème à résoudre. Ces expérimentations nous ont aussi permis d'affiner les situations que nous avons construites. / This research fits into the projects of the Maths à Modeler research team, especially in the one about Research Situation for the Classroom (Grenier and Payan, 2002 ; Ouvrier-Buffet, 2003 ; Godot, 2005 ; Cartier, 2008). One of our founding postulate is that knowing how to do mathematics is knowing how to solve partially reserch problems, the solving of such problems requiring experimental phases. Our problematic is about the teaching of the knowledge "experimental approach in mathematics" and the role that this knowledge plays in solving research problems. As we consider that this knowledge can only be learned by its practise, the aim of our research is the identification of epistemological and didactical conditions favouring the practise of the experimental approach in mathematics. Along with the building of a model of "situations" for the experimental approach, we built, analysed and experimented situations which refer to the model. We used the model of Research Situation for the Classroom (Grenier and Payan, 2002 ; Godot, 2005) and elements of the theory of didactical situation (Brousseau, 1998), especially a-didactical validation, didactical contract and "milieu". We have also defined a model of "experimental approach in mathematics" which was used as a "guide" of our research. After observing that "the experimental approach in mathematics", as we defined it, is not proposed by schools, experimentations and analyses showed that, in a certain way, students can do experimental approach in mathematics. Moreover, this practise let students progress in finding solutions thanks to the improvement of their conceptions about the problem. These experimentations also let us refined the situations that we have built.

In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and cycles, graphs with double domination numbers of 3, and graphs with double domination numbers of 4 with maximum diameter.