Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by Károlyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...

Title: Preference Top-k Search Based on Multidimensional B-Tree Author: RNDr. Matúš Ondreička Department: Department of Software Engineering Faculty of Mathematics and Physics Charles University in Prague Supervisor: Prof. RNDr. Jaroslav Pokorný, CSc. Author's e-mail address: ondreicka@ksi.mff.cuni.cz Supervisor's e-mail address: pokorny@ksi.mff.cuni.cz Abstract: In this thesis, we focus on the top-k search according to user pref- erences by using B+ -trees and the multidimensional B-tree (MDB-tree). We use model of user preferences based on fuzzy functions, which enable us to search according to a non-monotone ranking function. We propose model of sorted list based on the B+ -tree, which enables Fagin's algorithms to search for the top-k objects according to a non-monotone ranking function. We apply this model in the Internet environment with data on different remote servers. Furthermore, we designed novel dynamic tree-based data structures, namely, MDB-tree composed of B+ -trees, MDB-tree with lists, MDB-tree with groups of B+ -trees and multiple-ordered MDB-tree. Concurrently, we have developed novel top-k algorithms, namely, the MD algorithm, the MXT algorithm and their variants which are able search for the top-k objects ac- cording to a non-monotone ranking function. These top-k algorithms are efficient...

Název práce: Geometrické lineární a nelineární problémy prostor· funkcí Autor: Petr Petráček Katedra: Katedra matematické analýzy 'kolitel: prof. RNDr. Jaroslav Lukeš, DrSc., Katedra matematické analýzy Abstrakt: Tato práce sestává ze čtyř vědeckých článk·. lánky prezentované v prvních dvou kapitolách se věnují teorii reálných a komplexních L1-preduál·. lánky prezentované v třetí a čtvrté kapitole jsou věnovány problematice line- ability a algebrability podmnožin reálných funkcí a měr. V Kapitole 1 předsta- vujeme charakterizaci komplexních L1-preduál· pomocí komplexního barycent- rického zobrazení. Tato charakterizace je přirozeným rozšířením charakterizace reálných L1 preduál· pocházející od Bednara a Laceyho. V Kapitole 2 odpoví- dáme na otázku položenou Laceym v roce 1973. Dokazujeme přitom existenci kompaktního prostoru K a uzavřeného podprostoru H ⊂ C(K) obsahujícího kon- stantní funkce, pro který platí ∂HK = K, H je maximální vzhledem k ∂HK a H není L1-preduál. V Kapitole 3 se věnujeme lineabilitě množin nikde mono- tonních znaménkových Radonových měr na Rd . Konkrétně dokazujeme existence vektorového prostoru dimenze c jehož každý nenulový prvek je nikde monotonní míra absolutně spojitá vzhledem k d-rozměrné Lebesgueově míře. Nadto dokazu- jeme, že existuje takový lineární prostor, který je hustý...

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-25T17:20:25Z No. of bitstreams: 1 ANNAXSUEL ARAÚJO DE LIMA - DISSERTAÇÃO PPGMAT 2011..pdf: 581866 bytes, checksum: cc44cd422d4a48ddad0354f215805918 (MD5) / Made available in DSpace on 2018-07-25T17:20:25Z (GMT). No. of bitstreams: 1 ANNAXSUEL ARAÚJO DE LIMA - DISSERTAÇÃO PPGMAT 2011..pdf: 581866 bytes, checksum: cc44cd422d4a48ddad0354f215805918 (MD5) Previous issue date: 2011-04 / Neste trabalho, apresentamos métodos envolvendo sub e supersolução para estudar a existência de solução de certas equações elípticas. / In this work, we present methods involving sub and supersolution to study the existence of solution of certain elliptic equations.

Les phénomènes de contact entre les corps, déformables ou non, sont omniprésents dans la vie courante. Leurs modélisations requièrent des outils mathématiques faisant appel à des systèmes d'équations aux dérivées partielles incluant des conditions aux limites non triviales pour décrire le contact. Si les aspects physiques de la mécanique du contact sont connus depuis longtemps, la théorie mathématique qui lui est dédiée reste relativement récente laissant ainsi place à de nombreux problèmes à investiguer. Ce travail porte sur la modélisation, l'analyse et la simulation numérique de tels problèmes. Il se situe à mi-chemin entre la mécanique du contact et les aspects mathématiques inhérents au type de problème qui en découle. L'objectif est ici d'étudier certaines catégories de problèmes faisant intervenir des conditions originales de contact (avec et sans frottement) à la fois d'un point de vue mathématique et numérique, afin d'apporter une contribution à la théorie mathématique, puis de mettre en avant quelques méthodes numériques adaptées à leur résolution dans un cadre spécifique. / Contact phenomena between bodies, whether they are deformable or not, abound in everyday life. Their modellings require mathematical tools using systems of partial differential equations and involving complex boundary conditions, in order to describe the contact. While the physical aspects of such phenomena have been known for a long time, the mathematical theory remains relatively recent which leaves room for numerous problems. This work focuses on the modelling, the analysis and the numerical simulations of such problems. It is located halfway between contact mechanics and the mathematical aspects inherent to the mechanical questions involved. Our aim is to study several groups of problems that include original contact conditions (with or without friction), both from a mathematical and numerical point of view, in order to contribute to the theory, and also to highlight several numerical methods used to solve specific contact problems.

This paper offers an existence result for finite dimensional stochastic differential inclusions with maximal monotone drift and diffusion terms. Kravets studied only set-valued drifts in [5], whereas Motyl [4] additionally observed set-valued diffusions in an infinite dimensional context. In the proof we make use of the Yosida approximation of maximal monotone operators to achieve stochastic differential equations which are solvable by a theorem of Krylov and Rozovskij [7]. The selection property is verified with certain properties of the considered set-valued maps. Concerning Lipschitz continuous set-valued diffusion terms, uniqueness holds. At last two examples for application are given.

Stochastic differential inclusions can be considered as a generalisation of stochastic differential equations. In particular a multivalued mapping describes the set of equations, in which a solution has to be found. This paper presents an existence result for a special parabolic stochastic inclusion. The proof is based on the method of upper and lower solutions. In the deterministic case this method was effectively introduced by S. Carl.

In the work we modify the well-known minimal surface problem to a very special form, where the exponent two is replaced by a general positive parameter. To the modified problem we define four notions of solution in nonreflexive Sobolev space and in the space of functions of bounded variation. We examine the relationships between these notions to show that some of them are equivalent and some are weaker. After that we look for assumptions needed to prove the existence of solution to the problem in the sense of definitions provided. We outline that in the setting of spaces of functions of bounded variation the solution exists for any positive finite parameter and that if we accept some restrictions on the parameter then the solution exists in the Sobolev space, too. We also provide counterexample indicating that if the domain is non-convex, the solution in Sobolev space need not exist. Powered by TCPDF (www.tcpdf.org)

Dans une première partie, nous étudions la cohérence dans les systèmes transactionnels, en nous concentrant sur le problème de réconcilier la scalabilité avec des garanties transactionnelles fortes. Nous identifions quatre propriétés critiques pour la scalabilité. Nous montrons qu’aucun des critères de cohérence forte existants n’assurent l’ensemble de ces propriétés. Nous définissons un nouveau critère, appelé Non-Monotonic Snapshot Isolation ou NMSI, qui est le premier à être compatible avec les quatre propriétés à la fois. Nous présentons aussi une mise en œuvre de NMSI, appelée Jessy, que nous comparons expérimentalement à plusieurs critères connus. Une autre contribution est un canevas permettant de comparer de façon non biaisée différents protocoles. Elle se base sur la constatation qu’une large classe de protocoles transactionnels distribués est basée sur une même structure, Deferred Update Replication(DUR). Les protocoles de cette classe ne diffèrent que par les comportements spécifiques d’un petit nombre de fonctions génériques. Nous présentons donc un canevas générique pour les protocoles DUR.La seconde partie de la thèse a pour sujet la cohérence dans les systèmes de stockage non transactionnels. C’est ainsi que nous décrivons Tuba, un stockage clef-valeur qui choisit dynamiquement ses répliques selon un objectif de niveau de cohérence fixé par l’application. Ce système reconfigure automatiquement son ensemble de répliques, tout en respectant les objectifs de cohérence fixés par l’application, afin de s’adapter aux changements dans la localisation des clients ou dans le débit des requête. / In the first part, we study consistency in a transactional systems, and focus on reconciling scalability with strong transactional guarantees. We identify four scalability properties, and show that none of the strong consistency criteria ensure all four. We define a new scalable consistency criterion called Non-Monotonic Snapshot Isolation (NMSI), while is the first that is compatible with all four properties. We also present a practical implementation of NMSI, called Jessy, which we compare experimentally against a number of well-known criteria. We also introduce a framework for performing fair comparison among different transactional protocols. Our insight is that a large family of distributed transactional protocols have a common structure, called Deferred Update Replication (DUR). Protocols of the DUR family differ only in behaviors of few generic functions. We present a generic DUR framework, called G-DUR. We implement and compare several transactional protocols using the G-DUR framework.In the second part, we focus on ensuring consistency in non-transactional data stores. We introduce Tuba, a replicated key-value store that dynamically selects replicas in order to maximize the utility delivered to read operations according to a desired consistency defined by the application. In addition, unlike current systems, it automatically reconfigures its set of replicas while respecting application-defined constraints so that it adapts to changes in clients’ locations or request rates. Compared with a system that is statically configured, our evaluation shows that Tuba increases the reads that return strongly consistent data by 63%.

Cette thèse porte essentiellement sur l'étude d'algorithmes d'optimisation. Les problèmes de programmation intervenant en apprentissage automatique ou en traitement du signal sont dans beaucoup de cas composites, c'est-à-dire qu'ils sont contraints ou régularisés par des termes non lisses. Les méthodes proximales sont une classe d'algorithmes très efficaces pour résoudre de tels problèmes. Cependant, dans les applications modernes de sciences des données, les fonctions à minimiser se représentent souvent comme une espérance mathématique, difficile ou impossible à évaluer. C'est le cas dans les problèmes d'apprentissage en ligne, dans les problèmes mettant en jeu un grand nombre de données ou dans les problèmes de calcul distribué. Pour résoudre ceux-ci, nous étudions dans cette thèse des méthodes proximales stochastiques, qui adaptent les algorithmes proximaux aux cas de fonctions écrites comme une espérance. Les méthodes proximales stochastiques sont d'abord étudiées à pas constant, en utilisant des techniques d'approximation stochastique. Plus précisément, la méthode de l'Equation Differentielle Ordinaire est adaptée au cas d'inclusions differentielles. Afin d'établir le comportement asymptotique des algorithmes, la stabilité des suites d'itérés (vues comme des chaines de Markov) est étudiée. Ensuite, des généralisations de l'algorithme du gradient proximal stochastique à pas décroissant sont mises au point pour resoudre des problèmes composites. Toutes les grandeurs qui permettent de décrire les problèmes à résoudre s'écrivent comme une espérance. Cela inclut un algorithme primal dual pour des problèmes régularisés et linéairement contraints ainsi qu'un algorithme d'optimisation sur les grands graphes. / This thesis mainly studies optimization algorithms. Programming problems arising in signal processing and machine learning are composite in many cases, i.e they exhibit constraints and non smooth regularization terms. Proximal methods are known to be efficient to solve such problems. However, in modern applications of data sciences, functions to be minimized are often represented as statistical expectations, whose evaluation is intractable. This cover the case of online learning, big data problems and distributed computation problems. To solve this problems, we study in this thesis proximal stochastic methods, that generalize proximal algorithms to the case of cost functions written as expectations. Stochastic proximal methods are first studied with a constant step size, using stochastic approximation techniques. More precisely, the Ordinary Differential Equation method is adapted to the case of differential inclusions. In order to study the asymptotic behavior of the algorithms, the stability of the sequences of iterates (seen as Markov chains) is studied. Then, generalizations of the stochastic proximal gradient algorithm with decreasing step sizes are designed to solve composite problems. Every quantities used to define the optimization problem are written as expectations. This include a primal dual algorithm to solve regularized and linearly constrained problems and an optimization over large graphs algorithm.