This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Q_d of bounded average degree such that G does not contain a copy of Q_m but, for every G' such that G ⊊ G' ⊆ Q_d, the graph G' contains a copy of Q_m. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2^{(1-ε)k} subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2^{(1+o(1))^ck} for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q_m in Q_d. That is, we determine the minimum number of edges in a spanning subgraph G of Q_d such that the edges of E(Q_d)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q_m. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A₀ of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A₀ percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Q_d has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽_qⁿordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (ε_i)^∞_i=1 tending to zero such that, for all i ≥ 1, every weak ε_i-regular partition of W has at least exp(ε_i^-2/2^{5log∗ε_i^-2}) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤ_p such that any two adjacent vertices are mapped to elements of ℤ_p at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.

Esta Dissertação irá apresentar a utilização de técnicas de controle nãolinear, tais como o controle adaptativo e robusto, de modo a controlar um sistema de Eletroestimulação Funcional desenvolvido pelo laboratório de Engenharia Biomédica da COPPE/UFRJ. Basicamente um Eletroestimulador Funcional (Functional Electrical Stimulation FES) se baseia na estimulação dos nervos motores via eletrodos cutâneos de modo a movimentar (contrair ou distender) os músculos, visando o fortalecimento muscular, a ativação de vias nervosas (reinervação), manutenção da amplitude de movimento, controle de espasticidade muscular, retardo de atrofias e manutenção de tonicidade muscular. O sistema utilizado tem por objetivo movimentar os membros superiores através do estímulo elétrico de modo a atingir ângulos-alvo pré-determinados para a articulação do cotovelo. Devido ao fato de não termos conhecimento pleno do funcionamento neuro-motor humano e do mesmo ser variante no tempo, não-linear, com parâmetros incertos, sujeito a perturbações e completamente diferente para cada indivíduo, se faz necessário o uso de técnicas de controle avançadas na tentativa de se estabilizar e controlar esse tipo de sistema. O objetivo principal é verificar experimentalmente a eficácia dessas técnicas de controle não-linear e adaptativo em comparação às técnicas clássicas, de modo a alcançar um controle mais rápido, robusto e que tenha um desempenho satisfatório. Em face disso, espera-se ampliar o campo de utilização de técnicas de controle adaptativo e robusto, além de outras técnicas de sistemas inteligentes, tais como os algoritmos genéticos, provando que sua aplicação pode ser efetiva no campo de sistemas biológicos e biomédicos, auxiliando assim na melhoria do tratamento de pacientes envolvidos nas pesquisas desenvolvidas no Laboratório de Engenharia Biomédica da COPPE/UFRJ. / This dissertation will present the use of nonlinear control techniques, such as adaptive and robust control in order to design a Functional Electrical Stimulation (FES) system developed by Biomedical Engineering Laboratory at COPPE/UFRJ. Basically, a FES on the stimulation of motor nerves via skin electrodes in order to contract or stretch the muscles such that the amplitude and quality of the limbs movement can be maintained, reducing muscular atrophy as well. Consequently, the muscle strength can be improved and new neural pathways may be activated. Here, the goals of the proposed control system is to move the arm of the patient via electrical stimulation to achieve some desired trajectory related to the elbow angles of reference. Since we have a priori no deep knowledge of human neuro-motor model, the use of advanced and robust control schemes seems to be useful to stabilize this kind of systems which may be completely different for each individual, being time-varying, nonlinear, uncertain and subject to disturbances. The main objective is to experimentally verify the effectiveness of the proposed nonlinear and adaptive controllers when compared to classical ones in order to achieve faster, robust and better control performance. It is expected to spread the application of adaptive and robust controllers and other intelligent system tools, such as genetic algorithms, to the field of biological and biomedical engineering. Thus, we believe that the developed control system may help the improvement of the patients treatment involved in the research carried out by Biomedical Engineering Laboratory at COPPE/UFRJ.

Esta Dissertação irá apresentar a utilização de técnicas de controle nãolinear, tais como o controle adaptativo e robusto, de modo a controlar um sistema de Eletroestimulação Funcional desenvolvido pelo laboratório de Engenharia Biomédica da COPPE/UFRJ. Basicamente um Eletroestimulador Funcional (Functional Electrical Stimulation FES) se baseia na estimulação dos nervos motores via eletrodos cutâneos de modo a movimentar (contrair ou distender) os músculos, visando o fortalecimento muscular, a ativação de vias nervosas (reinervação), manutenção da amplitude de movimento, controle de espasticidade muscular, retardo de atrofias e manutenção de tonicidade muscular. O sistema utilizado tem por objetivo movimentar os membros superiores através do estímulo elétrico de modo a atingir ângulos-alvo pré-determinados para a articulação do cotovelo. Devido ao fato de não termos conhecimento pleno do funcionamento neuro-motor humano e do mesmo ser variante no tempo, não-linear, com parâmetros incertos, sujeito a perturbações e completamente diferente para cada indivíduo, se faz necessário o uso de técnicas de controle avançadas na tentativa de se estabilizar e controlar esse tipo de sistema. O objetivo principal é verificar experimentalmente a eficácia dessas técnicas de controle não-linear e adaptativo em comparação às técnicas clássicas, de modo a alcançar um controle mais rápido, robusto e que tenha um desempenho satisfatório. Em face disso, espera-se ampliar o campo de utilização de técnicas de controle adaptativo e robusto, além de outras técnicas de sistemas inteligentes, tais como os algoritmos genéticos, provando que sua aplicação pode ser efetiva no campo de sistemas biológicos e biomédicos, auxiliando assim na melhoria do tratamento de pacientes envolvidos nas pesquisas desenvolvidas no Laboratório de Engenharia Biomédica da COPPE/UFRJ. / This dissertation will present the use of nonlinear control techniques, such as adaptive and robust control in order to design a Functional Electrical Stimulation (FES) system developed by Biomedical Engineering Laboratory at COPPE/UFRJ. Basically, a FES on the stimulation of motor nerves via skin electrodes in order to contract or stretch the muscles such that the amplitude and quality of the limbs movement can be maintained, reducing muscular atrophy as well. Consequently, the muscle strength can be improved and new neural pathways may be activated. Here, the goals of the proposed control system is to move the arm of the patient via electrical stimulation to achieve some desired trajectory related to the elbow angles of reference. Since we have a priori no deep knowledge of human neuro-motor model, the use of advanced and robust control schemes seems to be useful to stabilize this kind of systems which may be completely different for each individual, being time-varying, nonlinear, uncertain and subject to disturbances. The main objective is to experimentally verify the effectiveness of the proposed nonlinear and adaptive controllers when compared to classical ones in order to achieve faster, robust and better control performance. It is expected to spread the application of adaptive and robust controllers and other intelligent system tools, such as genetic algorithms, to the field of biological and biomedical engineering. Thus, we believe that the developed control system may help the improvement of the patients treatment involved in the research carried out by Biomedical Engineering Laboratory at COPPE/UFRJ.

Considere um meio caracterizado por $N$ pontos cujas coordenadas são geradas aleatoriamente de maneira uniforme nas arestas unitárias de um hipercubo $d$-dimensional. Um caminhante parte de cada ponto deste meio desordenado e se movimenta obedecendo à regra determinista de ir para o ponto mais próximo que não tenha sido visitado nos últimos $mu$ passos. Este processo foi denominado de caminhada determinista do turista. Cada trajetória gerada por esta dinâmica possui uma parte inicial não-periódica de $t$ passos (transiente) e uma parte final periódica de $p$ passos (atrator). As probabilidades de vizinhança são expressas através da fórmula de Cox, que é parametrizada pela função beta incompleta normalizada $I_d = I_{1/4}[1/2,(d+1)/2]$. Enfati-zamos aqui que a distribuição relevante é $S_{mu,d}^{(N)}(t,p)$, a distribuição conjunta de $t$ e $p$, que tem como casos particulares as distribuições marginais, previamente estudadas. O objetivo deste estudo é obter analiticamente estas distribuições para a caminhada determinista do turista sem memória no espaço euclideano, no modelo de distâncias aleatórias (que corresponde ao limite $d ightarrow infty$) e no modelo de mapeamento aleatório (que é um caso limite das redes de Kauffman). As distribuições analíticas obtidas foram validadas através de experimentos numéricos. A distribuição conjunta de tempos de transiente e período de atratores, no limite termodinâmico para uma dimensionalidade arbitrária vale: $S_{1,d}^{(infty)}(t,p) = [Gamma(1+I_d^{-1}) cdot (t+I_d^{-1})/Gamma(t+p+I_d^{-1})] cdot delta_{p,2}$, onde $t=0,1,2,ldots,infty$; $Gamma(z)$ é a função gama e $delta_{i,j}$ é o delta de Kronecker. A caminhada determinista do turista sem memória no modelo de mapeamento aleatório produz uma distribuição de períodos não-trivial ($S_{0,rm}^{(N)}(p) propto p^{-1}$), que é obtida de $S_{0,rm}^{(N)}(t,p) = Gamma(N)/{Gamma[N+1-(t+p)]N^{t+p}}$, onde enfatizamos que o número de pontos explorados $n_e=t+p$ é a grandeza fundamental nos problemas considerados. / Consider a medium characterized by $N$ points whose coordinates are randomly generated by a uniform distribution along the unitary edges of a $d$-dimensional hypercube. A walker leaves from each point of this disordered medium and moves according to the deterministic rule to go the nearest point which has not been visited in the preceding $mu$ steps. This process has been called the deterministic tourist walk. Each trajectory generated by this dynamics has an initial non-periodic part of $t$ steps (transient) and a final periodic part of $p$ steps (attractor). The neighborhood probabilities are given by the Cox formula, which is parameterized by the normalized incomplete beta function $I_d = I_{1/4}[1/2,(d+1)/2]$. Here we stress that the relevant distribution is the joint $t$ and $p$ distribution $S_{mu,d}^{(N)}(t,p)$, which has as particular cases, the marginal distributions previously studied. The objective of this study is to obtain analytically these distributions for the memoryless deterministic tourist walk in the euclidean space, random link model (which corresponds to $d ightarrow infty$ limit) and random map model (which is a limiting case of the Kauffman model). The obtained distributions have been validated by numerical experiments. The joint transient time and attractor period distribution in the thermodynamic limit for an arbitrary dimensionality is: $S_{1,d}^{(infty)}(t,p) = [Gamma(1+I_d^{-1}) cdot (t+I_d^{-1})/Gamma(t+p+I_d^{-1})] cdot delta_{p,2}$, where $t=0,1,2,ldots,infty$; $Gamma(z)$ is the gamma function and $delta_{i,j}$ is the Kronecker's delta. The memoryless deterministic tourist walk in the random map leads to a non-trivial cycle distribution ($S_{0,rm}^{(N)}(p) propto p^{-1}$), which is obtained from $S_{0,rm}^{(N)}(t,p) = Gamma(N)/{Gamma[N+1-(t+p)]N^{t+p}}$, where we stress that the number of explored points $n_e=t+p$ is the fundamental quantity in the considered problems.

Dans tout ce qui suit, nous considérons une variété riemannienne compacte de dimension au moins égale à 2. A tout domaine (suffisamment régulier) , on peut associer la première valeur propre ?Ù de l’opérateur de Laplace-Beltrami avec condition de Dirichlet au bord. Nous dirons qu’un domaine est extrémal (sous entendu, pour la première valeur propre de l’opérateur de Laplace-Beltrami) si est un point critique de la fonctionnelle Ù? ?O sous une contrainte de volume V ol(Ù) = c0. Autrement dit, est extrémal si, pour toute famille régulière {Ot}te (-t0,t0) de domaines de volume constant, telle que Ù 0 = Ù, la dérivée de la fonction t ? ?Ot en 0 est nulle. Rappelons que les domaines extrémaux sont caractérisés par le fait que la fonction propre, associée à la première valeur propre sur le domaine avec condition de Dirichlet au bord, a une donnée de Neumann constante au bord. Ce résultat a été démontré par A. El Soufi et S. Ilias en 2007. Les domaines extrémaux sont donc des domaines sur lesquels peut être résolu un problème elliptique surdéterminé. L’objectif principal de cette thèse est la construction de domaines extrémaux pour la première valeur propre de l’opérateur de Laplace-Beltrami avec condition de Dirichlet au bord. Nous donnons des résultats d’existence de domaines extrémaux dans le cas de petits volumes ou bien dans le cas de volumes proches du volume de la variété. Nos résultats permettent ainsi de donner de nouveaux exemples non triviaux de domaines extrémaux. Le premier résultat que nous avons obtenu affirme que si une variété admet un point critique non dégénéré de la courbure scalaire, alors pour tout volume petit il existe un domaine extrémal qui peut être construit en perturbant une boule géodésique centrée en ce point critique non dégénéré de la courbure scalaire. La méthode que nous utilisons pour construire ces domaines extrémaux revient à étudier l’opérateur (non linéaire) qui à un domaine associe la donnée de Neumann de la première fonction propre de l’opérateur de Laplace-Beltrami sur le domaine. Il s’agit d’un opérateur (hautement non linéaire), nonlocal, elliptique d’ordre 1. Dans Rn × R/Z, le domaine cylindrique Br × R/Z, o`u Br est la boule de rayon r > 0 dans Rn, est un domaine extrémal. En étudiant le linéarisé de l’opérateur elliptique du premier ordre défini par le problème précédent et en utilisant un résultat de bifurcation, nous avons démontré l’existence de domaines extrémaux nontriviaux dans Rn × R/Z. Ces nouveaux domaines extrémaux sont proches de domaines cylindriques Br × R/Z. S’ils sont invariants par rotation autour de l’axe vertical, ces domaines ne sont plus invariants par translations verticales. Ce deuxi`eme r´esultat donne un contre-exemple à une conjecture de Berestycki, Caffarelli et Nirenberg énoncée en 1997. Pour de grands volumes la construction de domaines extrémaux est techniquement plus difficile et fait apparaître des phénomènes nouveaux. Dans ce cadre, nous avons dû distinguer deux cas selon que la première fonction propre Ø0 de l’opérateur de Laplace-Beltrami sur la variété est constante ou non. Les résultats que nous avons obtenus sont les suivants : 1. Si Ø0 a des points critiques non dégénérés (donc en particulier n’est pas constante), alors pour tout volume assez proche du volume de la variété, il existe un domaine extrémal obtenu en perturbant le complément d’une boule géodésique centrée en un des points critiques non dégénérés de Ø0. 2. Si Ø0 est constante et la variété admet des points critiques non dégénérés de la courbure scalaire, alors pour tout volume assez proche du volume de la variété il existe un domaine extrémal obtenu en perturbant le complément d’une boule géodésique centrée en un des points critiques non dégénérés de la courbure scalaire / In what follows, we will consider a compact Riemannian manifold whose dimension is at least 2. Let Ù be a (smooth enough) domain and ?O the first eigenvalue of the Laplace-Beltrami operator on Ù with 0 Dirichlet boundary condition. We say that Ù is extremal (for the first eigenvalue of the Laplace-Beltrami operator) if is a critical point for the functional Ù? ?O with respect to variations of the domain which preserve its volume. In other words, Ù is extremal if, for all smooth family of domains { Ù t}te(-t0,t0) whose volume is equal to a constant c0, and Ù 0 = Ù, the derivative of the function t ? ?Ot computed at t = 0 is equal to 0. We recall that an extremal domain is characterized by the fact that the eigenfunction associated to the first eigenvalue of the Laplace-Beltrami operator over the domain with 0 Dirichlet boundary condition, has constant Neumann data at the boundary. This result has been proved by A. El Soufi and S. Ilias in 2007. Extremal domains are then domains over which can be solved an elliptic overdeterminated problem. The main aim of this thesis is the construction of extremal domains for the first eigenvalue of the Laplace-Beltrami operator with 0 Dirichlet boundary condition. We give some existence results of extremal domains in the cases of small volume or volume closed to the volume of the manifold. Our results allow also to construct some new nontrivial exemples of extremal domains. The first result we obtained states that if the manifold has a nondegenerate critical point of the scalar curvature, then, given a fixed volume small enough, there exists an extremal domain that can be constructed by perturbation of a geodesic ball centered in that nondegenerated critical point of the scalar curvature. The methode used is based on the study of the operator that to a given domain associes the Neumann data of the first eigenfunction of the Laplace-Beltrami operator over the domain. It is a highly nonlinear, non local, elliptic first order operator. In Rn × R/Z, the circular-cylinder-type domain Br × R/Z, where Br is the ball of radius r > 0 in Rn, is an extremal domain. By studying the linearized of the elliptic first order operator defined in the previous problem, and using some bifurcation results, we prove the existence of nontrivial extremal domains in Rn × R/Z. Such extremal domains are closed to the circular-cylinder-type domains Br × R/Z. If they are invariant by rotation with respect to the vertical axe, they are not invariant by vertical translations. This second result gives a counterexemple to a conjecture of Berestycki, Caffarelli and Nirenberg stated in 1997. For big volumes the construction of extremal domains is technically more difficult and shows some new phenomena. In this context, we had to distinguish two cases, according to the fact that the first eigenfunction Ø0 of the Laplace-Beltrami operator over the manifold is constant or not. The results obtained are the following : 1. If Ø0 has a nondegenerated critical point (in particular it is not constant), then, given a fixed volume closed to the volume of the manifold, there exists an extremal domain obtained by perturbation of the complement of a geodesic ball centered in a nondegenerated critical point of Ø0. 2. If Ø0 is constant and the manifold has some nondegenerate critical points of the scalar curvature, then, for a given fixed volume closed to the volume of the manifold, there exists an extremal domain obtained by perturbation of the complement of a geodesic ball centered in a nondegenerate critical point of the scalar curvature

Orientador: Marcelo Carvalho Minhoto Teixeira / Resumo: Nesta tese, utiliza-se um otimizador analógico não derivativo proposto por Teixeira & Żak em 1999 como principal ferramenta para os sistemas de controle dos projetos desenvolvidos. Tal otimizador é composto por blocos não lineares e pode ser classificado como um sistema neural artificial. Sistemas chaveados têm grande aplicação prática na otimização de sistemas e são caracterizados por possuírem subsistemas e uma lei de chaveamento que seleciona cada subsistema a cada momento. Deve-se definir condições para que seja possível projetar uma lei de chaveamento que atenda requisitos de projeto. O estudo de técnicas de controle extremal na solução de problemas de busca pelo rastreamento do máximo ponto de potência (do inglês: Maximum Power Point Tracking - MPPT), vem apresentando resultados interessantes na literatura e um tipo de sistema à qual essa técnica pode ser aplicada, é na geração fotovoltaica. Aplica-se o otimizador analógico citado na busca do MPPT de uma célula fotovoltaica, com o objetivo de observar o controle extremal atuando em um processo de otimização, estendendo o controle para quando existem variações de irradiação solar (cenário de uma possível passagem de nuvens). Também observa-se o comportamento do sistema quanto a manter seu correto funcionamento e estabilidade ultimate bounded. A contribuição principal desta tese foi uma nova proposta de utilização conjunta do otimizador de Teixeira & Żak no projeto de controladores ˙ chaveados baseados na minimização da d... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: On this thesis, a non-derivative analog optimizer, proposed by Teixeira & Żak in 1999, was used as the main tool for the proposed control system. Such optimizer is structured by nonlinear blocks and can be classified as an artificial neural system. Switched systems have great theoretical and practical application in systems optimization and are characterized by having subsystems, and a switching law that selects each subsystem at each moment. It is necessary to define conditions so that it is possible to design a switching law for the desired performance of the controlled system. The study of Extremum Seeking Control techniques in the solution of problems of Maximum Power Point Tracking has presented interesting results, and one type of system which this technique can be applied is in the photovoltaic generation. The analog optimizer is applied in the Maximum Power Point Tracking of a photovoltaic cell, with the objective of observing the actuation of the extremal seeking control in an optimization process, extending the control when there are solar irradiation variations (a possible clouds passage scenario). And also observe the behavior of the system and how to maintain its correct functioning and ultimate bounded stability. The main contribution of this thesis was a new procedure for using the mentioned analog optimizer in the design of switched controllers based on the minimization of the derivative of a Lyapunov function. This method allows the relaxed design of controll... (Complete abstract click electronic access below) / Doutor

No description available.