In this thesis, we consider linear extremal problems in the Hp spaces. For many of these extremal problems, a unique solution can be guaranteed. We will examine some of the classical examples of extremal problems in these spaces. With this framework in place we will then consider a particular problem which does not always have a unique solution.

The problems we study in this thesis are all related to covering arrays. Covering arrays are combinatorial designs, widely used as templates for efficient interaction-testing suites. They have connections to many areas including extremal set theory, design theory, and graph theory. We define and study several generalizations of covering arrays, and we develop a method which produces an infinite family of LYM inequalities for graph-intersecting collections. A common theme throughout is the dependence of these problems on graphs. Our main contribution is an extremal method yielding LYM inequalities for $H$-intersecting collections, for every undirected graph $H$. Briefly, an $H$-intersecting collection is a collection of packings (or partitions) of an $n$-set in which the classes of every two distinct packings in the collection intersect according to the edges of $H$. We define ``$F$-following" collections which, by definition, satisfy a LYM-like inequality that depends on the arcs of a ``follow" digraph $F$ and a permutation-counting technique. We fully characterize the correspondence between ``$F$-following" and ``$H$-intersecting" collections. This enables us to apply our inequalities to $H$-intersecting collections. For each graph $H$, the corresponding inequality inherently bounds the maximum number of columns in a covering array with alphabet graph $H$. We use this feature to derive bounds for covering arrays with the alphabet graphs $S_3$ (the star on three vertices) and $\kvloop{3}$ ($K_3$ with loops). The latter improves a known bound for classical covering arrays of strength two. We define covering arrays on column graphs and alphabet graphs which generalize covering arrays on graphs. The column graph encodes which pairs of columns must be $H$-intersecting, where $H$ is a given alphabet graph. Optimizing covering arrays on column graphs and alphabet graphs is equivalent to a graph-homomorphism problem to a suitable family of targets which generalize qualitative independence graphs. When $H$ is the two-vertex tournament, we give constructions and bounds for covering arrays on directed column graphs. FOR arrays are the broadest generalization of covering arrays that we consider. We define FOR arrays to encompass testing applications where constraints must be considered, leading to forbidden, optional, and required interactions of any strength. We model these testing problems using a hypergraph. We investigate the existence of FOR arrays, the compatibility of their required interactions, critical systems, and binary relational systems that model the problem using homomorphisms.

A connected graph is total domination stable upon edge removal, if the removal of an arbitrary edge does not change the total domination number. We determine the minimum number of edges required for a total domination stable graph in terms of its order and total domination number.

[pt] Este trabalho, apresenta o estudo de uma lei de comando, proposta para um regulador extremal, capaz de regular três tipos de sistemas, ou seja: N-L, L-n, e L-N-nl, onde L é uma sistema linear de primeira ordem, e N é um sistema Não Linear que apresenta características parabólica, os blocos estão ligados em cascata, e é suposto que apenas a entrada e saída do conjunto, sejam acessíveis. O estudo foi feito por simulação analógica. No computador IBM-1130, utilizando para tanto o programa CSMP (continuous system modeling program). São apresentados e discutidos, os resultados gráficos, ilustrando as trajetórias e o comportamento dos três sistemas estudados, Quando sujeitos à lei de comando imposta pelo regulador. Estes resultados, levaram a concluir que, utilizando a lei de comando proposta, é possível, partindo de quaisquer condições iniciais, conduzir e faze com que os sistemas estudados, fiquem trabalhando no extremo da característica não linear, e que as oscilações, tanto em regime transitório como em regime permanente, são de amplitude dessprezível. / [en] This work presents the study of a control law for na extreme control regulator with the capability of controlling three types of systems, namely N-L, L-N, L-N and L-N-L, where L is a first-order linear system and N is a non-linear system that possesses a parabolic characteristic. The system blocks are interconnected in series and it is assumed that only the input and output terminals of the complete system are accessible. The study was made by an analogue simulation on the IBM-1130 computer, utilizing the CSMP (continuous system modeling program). The results are presented and discussed graphically and the curves illustrate the performance of the three systems when subject to the control law imposed by the regulator, these results lead to the conclusion that using the proposed control law it is possible to achieve control for any set of initial conditions. The transient and steady state responses show a very small amplitude of oscillation.

The classical Extreme Value Theory deals with independent random variables. If random variables are dependent, large values tend to cluster (that is, one large value is followed by a series of large values). It is of interest to describe probabilistically the clustering and estimate the relevant cluster functionals. We consider disjoint blocks, sliding blocks and runs estimators of cluster indices. Using a modern theory of multivariate, regularly varying time series, we obtain consistency results and central limit theorems under conditions that can be easily verified for a large class of short-range dependent models. In particular, we show that in the Peak-over-Threshold framework, all the estimators have the same limiting variances. This solves a longstanding open problem and is in contrast to the Block Maxima method. Our findings are illustrated by simulation experiments.

Thesis (MSc (Mathematics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: See full text for abstract / AFRIKAANSE OPSOMMING: Sien volteks vir opsomming

We show that finite de Finetti-type results may be viewed as results on the approximation of certain continuous functions of a parameter by a sequence of positive operators (Ln) . For distribtions that depend on a finite-dimensional statistic (Tn) only, Ln is the expectation operator of (Tn) under the extremal infinite exchangeable distributions. The rate of approximation of finite exchangeable distributions by mixtures of marginals of infinite exchangeable distributions is the rate of approximation of a single function of the parameter, namely the second indefinite integral of the Fisher information. Our results include a major part of what is known about finite de Finetti theorems. The theory is, however, not only valid for the case when the extremal infinite exchangeable distributions are products of identical distributions. It applies as well to Markov-exchangeable distributions or the linear model. Moreover, the metric is not restricted to the supremum norm. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

The capacity of a directed hypergraph is a particular numerical quantity associated with a hypergraph. It is of interest because of certain important connections to longstanding conjectures in theoretical computer science related to fast matrix multiplication and perfect hashing as well as various longstanding conjectures in extremal combinatorics. We give an overview of the concept of the capacity of a hypergraph and survey a few basic results regarding this quantity. Furthermore, we discuss the Lovász number of an undirected graph, which is known to upper bound the capacity of the graph (and in practice appears to be the best such general purpose bound). We then elaborate on some attempted generalizations/modifications of the Lovász number to undirected hypergraphs that we have tried. It is not currently known whether these attempted generalizations/modifications upper bound the capacity of arbitrary hypergraphs. An important method for proving lower bounds on hypergraph capacity is to exhibit a large independent set in a strong power of the hypergraph. We examine methods for this and show a barrier to attempts to usefully generalize certain of these methods to hypergraphs. We then look at cap sets: independent sets in powers of a certain hypergraph. We examine certain structural properties of them with the hope of finding ones that allow us to prove upper bounds on their size. Finally, we consider two interesting generalizations of capacity and use one of them to formulate several conjectures about connections between cap sets and sunflower-free sets.

Title: Extremal Polyominoes Author: Veronika Steffanová Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr. Abstract: The thesis is focused on polyominoes and other planar figures consisting of regular polygons, namely polyiamonds and polyhexes. We study the basic geometrical properties: the perimeter, the convex hull and the bounding rectangle/hexagon. We maximise and minimise these parameters and for the fixed size of the polyomino, denoted by n. We compute the extremal values of a chosen parameter and then we try to enumerate all polyominoes of the size n, which has the extremal property. Some of the problems were solved by other authors. We summarise their results. Some of the problems were solved by us, namely the maximal bounding rectan- gle/hexagon and maximal convex hull of polyiamonds. There are still sev- eral topics which remain open. We summarise the literature and offer our observations for the following scientists. Keywords: Polyomino, convex hull, extremal questions, plane 1

We give an overview of recent progress in the research of hypergraph jumps -- a problem from extremal combinatorics. The number $\alpha \in [0, 1)$ is a jump for $r$ if for any $\epsilon > 0$ and any integer $m \ge r$ any $r$-graph with $N > N(\epsilon, m)$ vertices and at least $(\alpha + \epsilon) {N \choose r}$ edges contains a subgraph with $m$ vertices and at least $(\alpha + c) {m \choose r}$ edges, where $c := c(\alpha)$ does depend only on $\alpha$. Baber and Talbot \cite{Baber} recently gave first examples of jumps for $r = 3$ in the interval $[2/9, 1)$. Their result uses the framework of flag algebras \cite{Raz07} and involves solving a semidefinite optimization problem. A software implementation of their method is a part of this work.