No description available.

We will survey some of the major directions of research in arithmetic combinatorics and their connections to other fields. We will then discuss three new results. The first result will generalize a structural theorem from Balog and Szemerédi. The second result will establish a new tool in incidence geometry, which should prove useful in attacking combinatorial estimates. The third result evolved from the famous sum-product problem, by providing a partial categorization of bivariate polynomial set functions which induce exponential expansion on all finite sets of real numbers.

No description available.

The study of pattern classes is the study of the involvement order on finite permutations. This order can be traced back to the work of Knuth. In recent years the area has attracted the attention of many combinatoralists and there have been many structural and enumerative developments. We consider permutations classes defined in three different ways and demonstrate that asking the same fixed questions in each case motivates a different view of involvement. Token passing networks encourage us to consider permutations as sequences of integers; grid classes encourage us to consider them as point sets; picture classes, which are developed for the first time in this thesis, encourage a purely geometrical approach. As we journey through each area we present several new results. We begin by studying the basic definitions of a permutation. This is followed by a discussion of the questions one would wish to ask of permutation classes. We concentrate on four particular areas: partial well order, finite basis, atomicity and enumeration. Our third chapter asks these questions of token passing networks; we also develop the concept of completeness and show that it is decidable whether or not a particular network is complete. Next we move onto grid classes, our analysis using generic sets yields an algorithm for determining when a grid class is atomic; we also present a new and elegant proof which demonstrates that certain grid classes are partially well ordered. The final chapter comprises the development and analysis of picture classes. We completely classify and enumerate those permutations which can be drawn from a circle, those which can be drawn from an X and those which can be drawn from some convex polygon. We exhibit the first uncountable set of closed classes to be found in a natural setting; each class is drawn from three parallel lines. We present a permutation version of the famous `happy ending' problem of Erdös and Szekeres. We conclude with a discussion of permutation classes in higher dimensional space.

The study of self-duality has attracted some attention over the past decade. A good deal of research in that time has been done on constructing and classifying all self-dual graphs and in particular polyhedra. We will give an overview of the recent research in the first two chapters. In the third chapter, we will show the necessary condition that a self-complementary self-dual graph have <i>n</i> &#8801; 0, 1 (mod 8) vertices and we will review White's infinite class (the Paley graphs, for which <i>n</i> &#8801; 1 (mod 8)). Finally, we will construct a new infinite class of self-complementary self-dual graphs for which <i>n</i> &#8801; 0 (mod 8).

The topic of this thesis is the hat problem. In this problem, a team of n players enters a room, and a blue or red hat is randomly placed on the head of each player. Every player can see the hats of all of the other players but not his own. Then each player must simultaneously guess the color of his own hat or pass. The team wins if at least one player guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of winning. This thesis is based on publications, which form the second chapter. In the first chapter we give an overview of the published results. In Section 1.1 we introduce to the hat problem and the hat problem on a graph, where vertices correspond to players, and a player can see the adjacent players. To the hat problem on a graph we devote the next few sections. First, we give some fundamental theorems about the problem. Then we solve the hat problem on trees, cycles, and unicyclic graphs. Next we consider the hat problem on graphs with a universal vertex. We also investigate the problem on graphs with a neighborhood-dominated vertex. In addition, we consider the hat problem on disconnected graphs. Next we investigate the problem on graphs such that the only known information are degrees of vertices. We also present Nordhaus-Gaddum type inequalities for the hat problem on a graph. In Section 1.6 we investigate the hat problem on directed graphs. The topic of Section 1.7 is the generalized hat problem with q &gt;= 2 colors. A modified hat problem is considered in Section 1.8. In this problem there are n &gt;= 3 players and two colors. The players do not have to guess their hat colors simultaneously and we modify the way of making a guess. We give an optimal strategy for this problem which guarantees the win. Applications of the hat problem and its connections to different areas of science are presented in Section 1.9. We also give there a comprehensive list of variations of the hat problem considered in the literature.

TITTLE: Mathematics on the chessboard AUTHOR: Jiří Šperl DEPARTMENT: The Department of mathematics and the teaching of mathematics SUPERVISOR: RNDr. Antonín Jančařík, Ph.D. ABSTRACT: The main subject of my thesis is mathematical problems on the chessboard using chess pieces. The work aims to demonstrate how a secondary school student would approach and solve several typical mathematical tasks of this nature. Consequently, it outlines ways to incorporate chessboard mathematical problems and exercises in mathematical classes. Moreover, the thesis includes a compact collection of solved problems on the chessboard that can serve as an inspiring source of unconventional mathematical tasks in conventional mathematical education. My own mathematical research forms a major part of the thesis. The research was conducted as a series of tests in three school classes. In order to achieve a high de- gree of objectivity classes of students with different specializations were selected to take part in the tests. The participating classes were also of different age groups. The theoretical part of the thesis takes a look at the past of the subject and presents several interesting historical problems concerning the mathematics on the chess- board. Last but not least, the thesis contains a discussion of solutions of the...

O objetivo deste trabalho é fazer um estudo amplo e sequencial sobre combinatória. Iniciase com os fundamentos da combinatória enumerativa, tais como permutações, combinações simples, combinações completas e os lemas de Kaplanski. Num segundo momento é apresentado uma abordagem aos problemas de contagem utilizando a teoria de conjuntos; são abordados o princípio da inclusão-exclusão, permutações caóticas e a contagem de funções. No terceiro momento é feito um aprofundamento do conceito de permutação sob a ótica da álgebra abstrata. É explorado o conceito de grupo de permutações e resultados importantes relacionados. Na sequência propõe-se uma relação de ordem completa e estrita para o grupo de permutações. Por fim, investiga-se dois problemas interessantes da combinatória: a determinação do número de caminhos numa malha quadriculada e a contagem de permutações que desconhecem padrões de comprimento três. / The objective of this work is to make a broad and sequential study on combinatorics. It begins with the foundations of enumerative combinatorics, such as permutations, simple combinations, complete combinations, and Kaplanskis lemmas. In a second moment an approach is presented to the counting problems using set theory; the principle of inclusion-exclusion, chaotic permutations and the counting of functions are addressed. In the third moment a deepening of the concept of permutation is made from the perspective of abstract algebra. The concept of group of permutations and related important results is explored. A strict total order relation for the permutation group is proposed. Finally, we investigate two interesting combinatorial problems: the determination of the number of paths in a grid and the number of permutations that avoids patterns of length three.

For a graph G = (V;E), a pebble distribution is defined as a mapping of the vertex set in to the integers, where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling distribution f if there exists some sequence of rubbling and pebbling moves that places a pebble on x. A pebbling distribution where every vertex is reachable is called a rubbling configuration. The t-restricted optimal rubbling number of G is the minimum number of pebbles required for a rubbling configuration where no vertex is initially assigned more than t pebbles. Here we present results on the 1-restricted optimal rubbling number and the 2- restricted optimal rubbling number.

The Hessenberg representation is a representation of the symmetric group afforded on the cohomology ring of a regular semisimple Hessenberg variety. We study this representation via a combinatorial presentation called GKM Theory. This presentation allows for the study of the representation entirely from a graph. The thesis derives a combinatorial construction of a basis of the equivariant cohomology as a free module over a polynomial ring. This generalizes classical constructions of Schubert classes and divided difference operators for the equivariant cohomology of the flag variety.