Let X be a space and let S ⊂ X with a measure of set size |S| and boundary size |∂S|. Fix a set C ⊂ X called the constraining set. The constrained isoperimetric problem asks when we can find a subset S of C that maximizes the Følner ratio FR(S) = |S|/|∂S|. We consider different measures for subsets of R^2,R^3,Z^2,Z^3 and describe the properties that must be satisfied for sets S that maximize the Folner ratio. We give explicit examples.

No description available.

No description available.

In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the edge isoperimetric value of G at I be defined as be(i,G)= mins v;|s|= i | δ(S,G)|. For S V, let φ(S,G) = {u ε V – S : ,such that be the vertex boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the vertex isoperimetric value of G at I be defined as bv(i,G)= The edge isoperimetric peak of G is defined as be(G) =. Similarly the vertex isoperimetric peak of G is defined as bv(G)= .The problem of determining a lower bound for the vertex isoperimetric peak in complete k-ary trees of depth d,Tdkwas recently considered in[32]. In the first part of this thesis we provide lower bounds for the edge and vertex isoperimetric peaks in complete k-ary trees which improve those in[32]. Our results are then generalized to arbitrary (rooted)trees. Let i be an integer where . For each i define the connected edge isoperimetric value and the connected vertex isoperimetric value of G at i as follows: is connected and is connected A meta-Fibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n-1))+ a(x2(n)+ a2′(n -2)), where xi: Z+ → Z+ , i =1,2, is a linear function of n and ai′(j)= a(j) or ai′(j)= -a(j), for i=1,2. Sequences belonging to this class have been well studied but in general their properties remain intriguing. In the second part of the thesis we show an interesting connection between the problem of determining and certain meta-Fibonacci sequences. In the third part of the thesis we study the problem of determining be and bv algorithmically for certain special classes of graphs. Definition 0.1. A tree decomposition of a graph G = (V,E) is a pair where I is an index set, is a collection of subsets of V and T is a tree whose node set is I such that the following conditions are satisfied: (For mathematical equations pl see the pdf file)

This thesis considers two isoperimetric inequalities for the eigenvalues of the Laplacian on a family of spherically symmetric Riemannian manifolds. The Payne-Pólya-Weinberger Conjecture (PPW) states that for a bounded domain Ω in Euclidean space Rn, the ratio λ1(Ω)/λ0(Ω) of the first two eigenvalues of the Dirichlet Laplacian is bounded by the corresponding eigenvalue ratio for the Dirichlet Laplacian on the ball BΩof equal volume. The Szegö-Weinberger inequality states that for a bounded domain Ω in Euclidean space Rn, the first nonzero eigenvalue of the Neumann Laplacian μ1(Ω) is maximized on the ball BΩ of the same volume. In the first three chapters we will look at the known work for the manifolds Rn and Hn. Then we will take a family a spherically symmetric manifolds given by Rn with a spherically symmetric metric determined by a radially symmetric function f. We will then give a PPW-type upper bound for the eigenvalue gap, λ1(Ω) − λ0(Ω), and the ratio λ1(Ω)/λ0(Ω) on a family of symmetric bounded domains in this space. Finally, we prove the Szegö-Weinberger inequality for this same class of domains.

<b>Asymptotic cones.</b> A finitely generated group has a word metric, which one can scale and thereby view the group from increasingly distant vantage points. The group coalesces to an "asymptotic cone" in the limit (this is made precise using techniques of non-standard analysis). The reward is that in place of the discrete group one has a continuous object "that is amenable to attack by geometric (e.g. topological, infinitesimal) machinery" (to quote Gromov). We give coarse geometric conditions for a metric space X to have N-connected asymptotic cones. These conditions are expressed in terms of certain filling functions concerning filling N-spheres in an appropriately coarse sense. We interpret the criteria in the case where X is a finitely generated group &Gamma; with a word metric. This leads to upper bounds on filling functions for groups with simply connected cones -- in particular they have linearly bounded filling length functions. We prove that if all the asymptotic cones of &Gamma; are N-connected then &Gamma; is of type F_N+1 and we provide N-th order isoperimetric and isodiametric functions. Also we show that the asymptotic cones of a virtually polycyclic group &Gamma; are all contractible if and only if &Gamma; is virtually nilpotent. <b>Combable groups and almost-convex groups.</b> A combing of a finitely generated group &Gamma; is a normal form; that is a choice of word (a combing line) for each group element that satisfies a geometric constraint: nearby group elements have combing lines that fellow travel. An almost-convexity condition concerns the geometry of closed balls in the Cayley graph for &Gamma;. We show that even the most mild combability or almost-convexity restrictions on a finitely presented group already force surprisingly strong constraints on the geometry of its word problem. In both cases we obtain an n! isoperimetric function, and upper bounds of ~ n² on both the minimal isodiametric function and the filling length function.

<p>In this dissertation we study combinatorial Hodge Laplacians on simplicial com-</p><p>plexes using tools generalized from spectral graph theory. Specifically, we consider</p><p>generalizations of graph Cheeger numbers and graph random walks. The results in</p><p>this dissertation can be thought of as the beginnings of a new spectral theory for</p><p>simplicial complexes and a new theory of high-dimensional expansion.</p><p>We first consider new high-dimensional isoperimetric constants. A new Cheeger-</p><p>type inequality is proved, under certain conditions, between an isoperimetric constant</p><p>and the smallest eigenvalue of the Laplacian in codimension 0. The proof is similar</p><p>to the proof of the Cheeger inequality for graphs. Furthermore, a negative result is</p><p>proved, using the new Cheeger-type inequality and special examples, showing that</p><p>certain Cheeger-type inequalities cannot hold in codimension 1.</p><p>Second, we consider new random walks with killing on the set of oriented sim-</p><p>plexes of a certain dimension. We show that there is a systematic way of relating</p><p>these walks to combinatorial Laplacians such that a certain notion of mixing time</p><p>is bounded by a spectral gap and such that distributions that are stationary in a</p><p>certain sense relate to the harmonics of the Laplacian. In addition, we consider the</p><p>possibility of using these new random walks for semi-supervised learning. An algo-</p><p>rithm is devised which generalizes a classic label-propagation algorithm on graphs to</p><p>simplicial complexes. This new algorithm applies to a new semi-supervised learning</p><p>problem, one in which the underlying structure to be learned is flow-like.</p> / Dissertation

Doctor of Philosophy / We consider the problem of minimising the eigenvalues of the Laplacian with Robin boundary conditions $\frac{\partial u}{\partial \nu} + \alpha u = 0$ and generalised Wentzell boundary conditions $\Delta u + \beta \frac{\partial u}{\partial \nu} + \gamma u = 0$ with respect to the domain $\Omega \subset \mathbb R^N$ on which the problem is defined. For the Robin problem, when $\alpha > 0$ we extend the Faber-Krahn inequality of Daners [Math. Ann. 335 (2006), 767--785], which states that the ball minimises the first eigenvalue, to prove that the minimiser is unique amongst domains of class $C^2$. The method of proof uses a functional of the level sets to estimate the first eigenvalue from below, together with a rearrangement of the ball's eigenfunction onto the domain $\Omega$ and the usual isoperimetric inequality. We then prove that the second eigenvalue attains its minimum only on the disjoint union of two equal balls, and set the proof up so it works for the Robin $p$-Laplacian. For the higher eigenvalues, we show that it is in general impossible for a minimiser to exist independently of $\alpha > 0$. When $\alpha < 0$, we prove that every eigenvalue behaves like $-\alpha^2$ as $\alpha \to -\infty$, provided only that $\Omega$ is bounded with $C^1$ boundary. This generalises a result of Lou and Zhu [Pacific J. Math. 214 (2004), 323--334] for the first eigenvalue. For the Wentzell problem, we (re-)prove general operator properties, including for the less-studied case $\beta < 0$, where the problem is ill-posed in some sense. In particular, we give a new proof of the compactness of the resolvent and the structure of the spectrum, at least if $\partial \Omega$ is smooth. We prove Faber-Krahn-type inequalities in the general case $\beta, \gamma \neq 0$, based on the Robin counterpart, and for the ``best'' case $\beta, \gamma > 0$ establish a type of equivalence property between the Wentzell and Robin minimisers for all eigenvalues. This yields a minimiser of the second Wentzell eigenvalue. We also prove a Cheeger-type inequality for the first eigenvalue in this case.

Doctor of Philosophy / We consider the problem of minimising the eigenvalues of the Laplacian with Robin boundary conditions $\frac{\partial u}{\partial \nu} + \alpha u = 0$ and generalised Wentzell boundary conditions $\Delta u + \beta \frac{\partial u}{\partial \nu} + \gamma u = 0$ with respect to the domain $\Omega \subset \mathbb R^N$ on which the problem is defined. For the Robin problem, when $\alpha > 0$ we extend the Faber-Krahn inequality of Daners [Math. Ann. 335 (2006), 767--785], which states that the ball minimises the first eigenvalue, to prove that the minimiser is unique amongst domains of class $C^2$. The method of proof uses a functional of the level sets to estimate the first eigenvalue from below, together with a rearrangement of the ball's eigenfunction onto the domain $\Omega$ and the usual isoperimetric inequality. We then prove that the second eigenvalue attains its minimum only on the disjoint union of two equal balls, and set the proof up so it works for the Robin $p$-Laplacian. For the higher eigenvalues, we show that it is in general impossible for a minimiser to exist independently of $\alpha > 0$. When $\alpha < 0$, we prove that every eigenvalue behaves like $-\alpha^2$ as $\alpha \to -\infty$, provided only that $\Omega$ is bounded with $C^1$ boundary. This generalises a result of Lou and Zhu [Pacific J. Math. 214 (2004), 323--334] for the first eigenvalue. For the Wentzell problem, we (re-)prove general operator properties, including for the less-studied case $\beta < 0$, where the problem is ill-posed in some sense. In particular, we give a new proof of the compactness of the resolvent and the structure of the spectrum, at least if $\partial \Omega$ is smooth. We prove Faber-Krahn-type inequalities in the general case $\beta, \gamma \neq 0$, based on the Robin counterpart, and for the ``best'' case $\beta, \gamma > 0$ establish a type of equivalence property between the Wentzell and Robin minimisers for all eigenvalues. This yields a minimiser of the second Wentzell eigenvalue. We also prove a Cheeger-type inequality for the first eigenvalue in this case.

Made available in DSpace on 2015-05-15T11:46:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-08-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work presents a research on problems of maxima and minima of the Euclidean geometry. Initially we present some preliminary results followed by statements that in essence use basic concepts of geometry. Below are some problems of maximizing area and minimizing perimeter of triangles and convex polygons, culminating in a proof of the isoperimetric inequality for polygons and review the general case. Solve some classical problems of geometry that are related to outliers and present other problems as proposed. / Este trabalho apresenta uma pesquisa sobre problemas de máximos e mínimos da Geometria Euclidiana. Inicialmente apresentamos alguns resultados preliminares seguidos de suas demonstrações que em sua essência usam conceitos básicos de geometria. Em seguida apresentamos alguns problemas de maximização de área e de minimização de perímetro em triângulos e polígonos convexos, culminando com uma prova da desigualdade isoperimétrica para polígonos e comentário do caso geral. Resolvemos alguns problemas clássicos de geometria que estão relacionados com valores extremos e apresentamos outros como problemas propostos.