Under approval voting, every voter may vote for any number of canditates. To model approval voting, we let a political spectrum be the set of all possible political positions, and let each voter have a subset of the spectrum that they approve, called an approval region. The fraction of all voters who approve the most popular position is the agreement proportion for the society. We consider voting in societies whose political spectrum is modeled by $d$-dimensional space ($\mathbb{R}^d$) with approval regions defined by axis-parallel boxes. For such societies, we first consider a Tur&#aacute;n-type problem, attempting to find the maximum agreement between pairs of voters for a society with a given level of overall agreement. We prove a lower bound on this maximum agreement and find in the literature a proof that the lower bound is optimal. By this result we find that for sufficiently large $n$, any $n$-voter box society in $\mathbb{R}^d$ where at least $\alpha\binom{n}{2}$ pairs of voters agree on some position must have a position contained in $\beta n$ approval regions, where $\alpha = 1-(1-\beta)^2/d$. We also consider an extension of this problem involving projections of approval regions to axes. Finally we consider the question of $(k,m)$-agreeable box societies, where a society is said to be $(k, m)$-agreeable if among every $m$ voters, some $k$ approve a common position. In the $m = 2k - 1$ case, we use methods from graph theory to prove that the agreement proportion is at least $(2d)^{-1}$ for any integer $k \ge 2.$

We show that the usual variational formulation of the problem of analytic continuation from an arc on the boundary of a plane domain does not lead to a relaxation of this overdetermined problem. To attain such a relaxation, we bound the domain of the functional, thus changing the Euler equations.

The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM property again. In 1974, Harper proved that if two finite standard graded posets satisfying the LYM properties also satisfy rank logarithmic concavities, then their product also satisfies these two properties. However, Harper's proof is rather non-intuitive. Giving a natural proof of Harper's theorem is one of the goals of this thesis. The main new result of this thesis is a characterization of rank-finite standard graded LYM posets that satisfy rank logarithmic concavities. With this characterization theorem, we are able to give a new, natural proof of Harper's theorem. In fact, we prove a strengthened version of Harper's theorem by weakening the finiteness condition to the rank-finiteness condition. We present some interesting applications of the main characterization theorem. We also give a brief history of Sperner theory, and summarize all the ingredients we need for the main theorem and its applications, including a new equivalent condition for the LYM property that is a key for proving our main theorem.

The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM property again. In 1974, Harper proved that if two finite standard graded posets satisfying the LYM properties also satisfy rank logarithmic concavities, then their product also satisfies these two properties. However, Harper's proof is rather non-intuitive. Giving a natural proof of Harper's theorem is one of the goals of this thesis. The main new result of this thesis is a characterization of rank-finite standard graded LYM posets that satisfy rank logarithmic concavities. With this characterization theorem, we are able to give a new, natural proof of Harper's theorem. In fact, we prove a strengthened version of Harper's theorem by weakening the finiteness condition to the rank-finiteness condition. We present some interesting applications of the main characterization theorem. We also give a brief history of Sperner theory, and summarize all the ingredients we need for the main theorem and its applications, including a new equivalent condition for the LYM property that is a key for proving our main theorem.

Extremal Functions for Graph Linkages and Rooted Minors Paul Wollan 137 pages Directed by: Robin Thomas A graph G is k-linked if for any 2k distinct vertices s_1,..., s_k,t_1,..., t_k there exist k vertex disjoint paths P_1,...,P_k such that the endpoints of P_i are s_i and t_i. Determining the existence of graph linkages is a classic problem in graph theory with numerous applications. In this thesis, we examine sufficient conditions that guarantee a graph to be k-linked and give the following theorems. (A) Every 2k-connected graph on n vertices with 5kn edges is k-linked. (B) Every 6-connected graph on n vertices with 5n-14 edges is 3-linked. The proof method for Theorem (A) can also be used to give an elementary proof of the weaker bound that 8kn edges suffice. Theorem (A) improves upon the previously best known bound due to Bollobas and Thomason stating that 11kn edges suffice. The edge bound in Theorem (B) is optimal in that there exist 6-connected graphs on n vertices with 5n-15 edges that are not 3-linked. The methods used prove Theorems (A) and (B) extend to a more general structure than graph linkages called rooted minors. We generalize the proof methods for Theorems (A) and (B) to find edge bounds for general rooted minors, as well as finding the optimal edge bound for a specific family of bipartite rooted minors. We conclude with two graph theoretical applications of graph linkages. The first is to the problem of determining when a small number of vertices can be used to cover all the odd cycles in a graph. The second is a simpler proof of a result of Boehme, Maharry and Mohar on complete minors in huge graphs of bounded tree-width.

Thesis (Ph. D.)--University of Washington, 1998. / Vita. Includes bibliographical references (p. [59]-61).

Thesis (Ph. D.)--University of Texas at Austin, 1999. / Vita. Includes bibliographical references (leaves 80-81). Available also in a digital version from Dissertation Abstracts.

In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of $\mathbb{Z}^n$. In this setting a tile $T$ is just a finite subset of $\mathbb{Z}^n$. We say that $T$ tiles $\mathbb{Z}^n$ if the latter set admits a partition into isometric copies of $T$. Chalcraft observed that there exist $T$ that do not tile $\mathbb{Z}^n$ but tile $\mathbb{Z}^{d}$ for some $d > n$. He conjectured that such $d$ exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset $P$ of size a power of $2$, if $P$ has a greatest and a least element, then there is a positive integer $k$ such that $[2]^k$ can be partitioned into copies of $P$. The third tiling problem is about vertex-partitions of the hypercube graph $Q_n$. Offner asked: if $G$ is a subgraph of $Q_n$ such $|G|$ is a power of $2$, must $V(Q_d)$, for some $d$, admit a partition into isomorphic copies of $G$? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set $P$ is a maximal collinear subset of $P$. P\'or and Wood considered colourings of finite $P$ without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that $|P|$ is large. They conjectured that for all $k,l \ge 2$ there exists an $n \ge 2$ such that if $|P| \ge n$ and $P$ does not contain a line of cardinality larger than $l$, then every colouring of $P$ with $k$ colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case $k=l=3$. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with $n$ vertices and $m$ edges? For sufficiently large $n$ we prove a conjecture of F\"uredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an $r$-uniform graph $H$ is to assign for each of its edges one of the $r!$ possible orderings of its elements. Then, for any $p$-set of vertices $A$ and any $p$-set of indices $I \subset [r]$, we define the $I$-degree of $A$ to be the number of edges containing vertices $A$ in precisely the positions labelled by $I$. Caro and Hansberg were interested in determining whether a given $r$-uniform hypergraph admits an orientation where every set of $p$ vertices has some $I$-degree equal to $0$. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for $r$ large, but false in general.

El tema que trata esta memoria de titulo es minimizar el primer valor propio de un conductor compuesto por dos materiales homogéneos, que son distribuidos en proporciones fijas dentro de un dominio. Los trabajos pioneros de F. Murat y L. Tartar [26] muestran que esta clase de problemas del cálculo de variaciones podrían tener existencia de minimizadores sólo en una clase más grande, llamada clase de materiales homogenizados o con micro-estructura, excluyendo a priori distribuciones clásicas de material como soluciones optimales. Para dominios en una dimensión, M. G. Krein [22] probó la existencia de una solución clásica. En dimensiones más altas, cuando el problema se restringe a una bola, A. Alvino, P. L. Trombetti y P. L. Lions [4] probaron que se pueden obtener soluciones clásicas radialmente simétricas. Sin embargo, estos resultados han sido vistos como excepcionales, atribuidos a la completa simetría del dominio. Cox y Lipton [11], sólo estudiaron condiciones para un diseño óptimo del problema asumiendo soluciones homogenizadas. Aún es desconocido si en dominios con simetría parcial es posible o no obtener una solución clásica que respete la simetría del dominio. Esperamos revivir el interés a esta pregunta dando una nueva prueba del resultado en una bola. Creemos además que, en este caso, distribuir el material de mayor conductividad en el centro es una solución óptima. En los primeros capítulos se introduce el problema y se hace un resumen crítico del estado del arte en lo que se refiere a la existencia de un minimizador, incluyendo algunas referencias clásicas que plantean la no existencia de solución para problemas similares. Luego se describen las principales herramientas utilizadas en el desarrollo de esta tesis. Se da un énfasis particular a los re-arreglos de funciones. En el capítulo cuarto se describe el problema general y en el quinto un análisis exhaustivo del problema en una dimensión. En el capítulo sexto se desarrolla el caso de una bola N dimensional, otorgando una nueva prueba de la existencia de una solución clásica radialmente simétrica. En el capítulo séptimo se desarrolla el cálculo de la derivada con respecto al dominio del primer valor propio, y en el octavo se muestran experiencias numéricas asociadas al problema, en el caso de un disco en R2. En el capítulo noveno se genera un análisis del signo de la derivada para el caso de una bola N dimensional, otorgando resultados, con los cuales se espera concluir, en un futuro próximo, que la solución del problema para este tipo de dominios, se encuentra disponiendo el material de más alta conductividad en el centro.

abstract: Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to find ex(n; F ) for various graphs F . The question can be further generalized by asking for the extreme values of other graph parameters like minimum degree, maximum degree, or connectivity. We call this type of question a Tura ́n-type problem. In this thesis, we will study Tura ́n-type problems and their variants for graphs and hypergraphs. Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs. In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures. Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2018