Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and Skokan, by W.T. Gowers, and subsequently, by T. Tao. These extensions have yielded quite a few non-trivial applications to Extremal Hypergraph Theory, Combinatorial Number Theory and Theoretical Computer Science. A main drawback to the hypergraph regularity techniques above is that they are highly technical. In this thesis, we consider a less technical version of hypergraph regularity which more directly generalizes Szemeredi's regularity lemma for graphs. The tools we discuss won't yield all applications of their stronger relatives, but yield still several applications in extremal hypergraph theory (for so-called linear or simple hypergraphs), including algorithmic ones. This thesis surveys these lighter regularity techiques, and develops three applications of them.

Kakutani’s fixed point theorem has many applications in economics and game theory. One of its most well known applications is in John Nash’s paper [8], where the theorem is used to prove the existence of an equilibrium strategy in n-person games. Sperner’s lemma, on the other hand, is a combinatorial result concerning the labelling of the vertices of simplices and their triangulations. It is known that Sperner’s lemma is equivalent to a result called Brouwer’s fixed point theorem, of which Kakutani’s theorem is a generalization. A natural question that arises is whether we can prove Kakutani’s fixed point theorem directly using Sperner’s lemma without going through Brouwer’s theorem. The objective of this thesis to understand Kakutani’s theorem, Sperner’s lemma, and how they are related. In particular, I explore ways in which Sperner’s lemma can be used to prove Kakutani’s theorem and related results.

The purpose of the thesis is to examine a selection of papyri from the large corpus of Euripides, Sophocles and Aristophanes. The study of the texts has been divided into three major chapters where each one of the selected papyri is first reproduced and then discussed. The transcription follows the original publication whereas any possible textual improvement is included in the commentary. The commentary also contains a general description of the papyrus (date, layout and content) as well reference to special characteristics. The structure of the commentary is not identical for marginalia and hypomnemata: the former are examined in relation to their position round the main text and are treated both as individual notes and as a group conveying the annotator's aims. The latter are examined lemma by lemma with more emphasis upon their origins and later appearances in scholia and lexica. After the study of the papyri follows an essay which summarizes the results and tries to incorporate them into the wider context of the history of the text of each author and the scholarly attention that this received by the Alexandrian scholars or later grammarians. The main effort is to place each papyrus into one of the various stages that scholarly exegesis passed especially in late antiquity. Special treatment has been given to P.Wurzburg 1, the importance of which made it necessary that it occupies a chapter by itself. The last chapter of the thesis deals with the issue of glosses, namely their origin and use in the margins of papyri. The focus is again on the history of early collections of tragic and comic vocabulary and their appearance in the margins or hypomnemata. The parallel circulation of hypomnemata and glossaries often compiled by the same people and some special features of the glosses in our material led to the conclusion that most glosses at least in the earlier periods were copied from hypomnemata. The thesis ends with a presentation of all conclusions from the previous chapters in relation to the history of scholarship and book production in late antiquity

The Kalman-Yakubovich-Popov (KYP) lemma is a useful tool in control and signal processing that allows an important family of computationally intractable semi-infinite programs in the entire frequency range to be characterized by computationally tractable semidefinite programs. The first part of this thesis presents a new variation of the frequency selective Kalman-Yakubovich-Popov (FS-KYP) lemma for single input single output systems, which generalizes the conventional KYP lemma on given frequency intervals. Based on the transfer function representation of single input single output systems, the proposed FS-KYP lemma provides a unified framework to convert an important family of semi-infinite programs with generic frequency selective constraints that arise from a variety of analysis and synthesis problems for infinite impulse response systems into semidefinite programs. In contrast to existing variations of the FS-KYP lemma, which invariably involves Lyapunov variables of large dimensions, the proposed FS-KYP lemma is free from Lyapunov variables. As a consequence, the proposed semidefinite programs require a minimal number of additional variables, thus can be efficiently solved by general purpose semidefinite programming solvers on a standard personal computer. The second part of this thesis studies several applications of the FS-KYP lemma to control and signal processing. Firstly, we investigate the beam pattern synthesis of an antenna array with bounded sidelobe and mainlobe levels. It is shown that the pattern synthesis problem can be posed as a convex semi-infinite program that is turned into an semidefinite program via the proposed FS-KYP lemma. The attractive feature of the proposed method is that our semidefinite program uses only a minimal number of auxiliary variables. This subsequently enables the design of patterns for arrays with several hundred elements to be achieved on a standard personal computer using existing SDP solvers. Secondly, we develop an efficient method to design several types of digital and analog infinite impulse response filters and filter banks via the new FS-KYP lemma. The proposed method is more flexible than analytical methods in the sense that it allows direct control of more design parameters, which in turn enables more requirements such as degree of flatness to be incorporated into the design process. Finally, we examine some applications of the new FS-KYP to robustness analysis of continuous control systems. Specifically, we introduce a new bisection method to compute the H∞ gain of uncertain polytopic systems.

Zugl.: Heidelberg, Univ., Diss., 2008

Wikipedia has a problem with organizing and managing data as well as references. As a solution, they created Wikidata to make it possible for machines to interpret these data, with the help of lexemes. A lexeme is an abstract lexical unit which consists of a word’s lemmas and its word class. The object of this paper is to present one possible way to provide Swedish lexeme data to Wikidata. This was implemented in two phases, namely, the first phase was to identify the lemmas and their word classes; the second phase was to process these words to create coherent lexemes. The developed model was able to process large amounts of words from the data source but barely succeeded to generate coherent lexemes. Although the lexemes was supposed to provide an efficient way of data understanding for machines, the obtained results lead to the conclusion that the developed model did not achieve the anticipated results. This is due to the amount of words found in correlation to the words processed. It is needed to find a way to import lexeme data to Wikidata from another data source.

No description available.

Neste trabalho reunimos alguns resultados afirmativos relacionados ao closing lemma de classe C^r em variedades bidimensionais compactas. / In this work we present some partial results corcerning closing lemma for smooth flows on compact bidimensional manifolds.

Ramsey Theorem, in the most simple form, states that if we are given a positive integer l, there exists a minimal integer r(l), called the Ramsey number, such any partition of the edges of K_r(l) into two sets, i.e. a 2-coloring, yields a copy of K_l contained entirely in one of the partitioned sets, i.e. a monochromatic copy of Kl. We prove an extension of Ramsey's Theorem, in the more general form, by replacing complete graphs by multipartite graphs in both senses, as the partitioned set and as the desired monochromatic graph. More formally, given integers l and k, there exists an integer p(m) such that any 2-coloring of the edges of the complete multipartite graph K_p(m);r(k) yields a monochromatic copy of K_m;k . The tools that are used to prove this result are the Szemeredi Regularity Lemma and the Blow Up Lemma. A full proof of the Regularity Lemma is given. The Blow-Up Lemma is merely stated, but other graph embedding results are given. It is also shown that certain embedding conditions on classes of graphs, namely (f , ?) -embeddability, provides a method to bound the order of the multipartite Ramsey numbers on the graphs. This provides a method to prove that a large class of graphs, including trees, graphs of bounded degree, and planar graphs, has a linear bound, in terms of the number of vertices, on the multipartite Ramsey number.

Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3. The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove an asymptotic minimum degree condition for an arbitrary bipartite graph G to be tiled by another arbitrary bipartite graph H. This proves a conjecture of Zhao and also implies an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.