We prove several inequalities involving the Fourier transform of functions which are compactly supported. The constraint that the functions have compact support is a simplifying feature which is desirable in applications, but there is a trade-off in control of other relevant quantities-- such as the mass of the function. With applications in mind, we prove inequalities which quantify these types of trade-offs. / text

Le spectre du Laplacien sans signe a fait l'objet de beaucoup d'attention dans la communauté scientifique ces dernières années. La principale raison est l'intuition, basée sur une étude des petits graphes et sur des propriétés valides pour des graphes de toutes tailles, que plus de graphes sont déterminés par le spectre de cette matrice que par celui de la matrice d'adjacence et du Laplacien. Les travaux présentés dans cette thèse ont apporté des éléments nouveaux sur les informations contenues dans le spectre cette matrice. D'une part, on y présente des relations entre les invariants de structure et une valeur propre du Laplacien sans signe. D'autre part, on présente des familles de graphes extrêmes pour deux de ses valeurs propres, avec et sans contraintes additionnelles sur la forme de graphe. Il se trouve que ceux-ci sont très similaires à ceux obtenus dans les mêmes conditions avec les valeurs propres de la matrice d'adjacence. Cela aboutit à la définition de familles de graphes pour lesquelles, le spectre du Laplacien sans signe ou une de ses valeurs propres, le nombre de sommets et un invariant de structure suffisent à déterminer le graphe. Ces résultats, par leur similitude avec ceux de la littérature viennent confirmer l'idée que le Laplacien sans signe détermine probablement aussi bien les graphes que la matrice d'adjacence.

Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}-matrices, sequences and sets of permutations, which found many ap- plications in combinatorial and computational geometry. The VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of n-element permutations with VC-dimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com- plete topological graphs on n vertices. For some, mostly permutation, matrices M, we give new bounds on the number of 1-entries an n × n M-avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries in matrices avoiding a fixed layered...

of doctoral thesis Structural graph theory Jan Hladký In the thesis we make progress on the Loebl-Komlós-Sós Conjecture which is a classic problem in the field of Extremal Graph Theory. We prove the following weaker version of the Conjecture: For every α > 0 there exists a number k0 such that for every k > k0 we have that every n-vertex graph G with at least (1 2 +α)n vertices of degrees at least (1+α)k contains each tree T of order k as a subgraph. The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we develop a decomposition technique that applies also to sparse graphs: each graph can be decomposed into vertices of huge degrees, regular pairs (in the sense of the Regularity Lemma), and two other components each exhibiting certain expander-like properties. The results were achieved in a joint work with János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein and Endre Szemerédi. 1

No description available.

No desenvolvimento de projetos de iluminação de ambientes, um dos objetivos que se destaca é a busca pelo conforto visual, que emprega metodologias de resolução conhecidas, como o Método dos Lumens e o Método Ponto a Ponto. A luz visível está contida no espectro da radiação térmica e, portanto, o fluxo luminoso pode ser relacionado ao fluxo de radiação térmica. Determinar as posições e as competências das fontes de luz necessárias na superfície de projeto ganha importância quando o comportamento, em termos de uniformidade ou de fluxo radiante, é especificado. O presente trabalho visa a estabelecer diferentes valores de fluxo em duas regiões distintas da superfície do projeto. Por meio do posicionamento das fontes de luz, é estabelecido um fluxo maior na região denominada principal e um fluxo menor na região denominada secundária. A modelagem matemática da radiação térmica (Método das Radiosidades) é aplicada ao projeto de iluminação, considerando-se as características da visão humana e o comportamento das fontes de luz. Na modelagem, é considerada uma cavidade retangular tridimensional com superfícies cinza e com condição de parede fria, na qual o poder emissivo das paredes é nulo. As fontes de luz são representadas por unidades de malha no teto. A relação de equações é resolvida por metodologia inversa, usando o algoritmo de Otimização Extrema Generalizada (GEO). Este algoritmo é classificado como um método de otimização estocástica de busca global para a resolução de sistemas considerados inicialmente mal condicionados. A posição e a potência das fontes luminosas são determinadas pela resolução do sistema de equações, de forma a proporcionar um fluxo de radiação duas vezes maior na região principal em relação à região secundária. A função objetivo do processo consiste em minimizar a diferença entre o fluxo desejado e os valores de fluxo de radiação incidente nas duas regiões da superfície de projeto. Em virtude das características de simetria do problema, a relação é estabelecida para apenas um quarto da cavidade. Assim, por exemplo, aplicar a metodologia com 9 fontes de luz a um quarto da região resulta em 36 fontes de luz em toda a cavidade. Os resultados mostram que é possível encontrar um arranjo de fontes de luz preestabelecendo-se duas condições de potência. / In the development of environmental illumination projects, one of the main goals to be achieved is the visual comfort, which is usually done by known methodologies, like the Lumens Method and the Point by Point Method. Since the visible light is contained in the spectrum of thermal radiation, the luminous flux can be related to the thermal radiation flux. The determination of the position and power of the light sources required by the design surface gains an higher importance whenever a behavior is specified, should it be in terms of uniformity or in therms of radiant flux. In this work, we describe a method that allows the establishment of different flux values in two distinct regions of the design surface, which are referred by the names main region and secondary region. Through the spatial arrangement of the light sources, the method sets a more intense flux in the main region and a less intense one in the secondary region. The mathematical model of thermal radiation, known as Radiosity Method, is applied to the illumination design, along with the characteristics of the human vision and the behavior of light sources. In this model, a rectangular three-dimensional cavity is considered. It has gray surfaces and exhibits the conditions of a cold wall, in which the emissivity power of the walls is null. The light sources are represented by a mesh unit in the ceiling. The system of equations is solved by inversemethodology, using the Generalized Extremal Optimization (GEO) algorithm. This algoritm is classified as being a stochastic optimization method of global search to solve systems that are initially considered ill-conditioned. By solving this system, the position and power of light sources can be determined, and this is done in such a way that the flux radiation in the main region is twice more intense then the one in the secondary region. The target function of the whole process is to minimize the difference between the desired flux and the incident flux radiation values for each one of the two design surface regions. We further explore the problem symmetry, solving the equation system for only a quarter of the cavity. This way, if the methodology is applied with nine light sources into a quarter of the region, the entire cavity will behave as if it has 36 light sources. Our results show that, given two prescribed conditions of power, it is possible to find an arrangement of light sources.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

No desenvolvimento de projetos de iluminação de ambientes, um dos objetivos que se destaca é a busca pelo conforto visual, que emprega metodologias de resolução conhecidas, como o Método dos Lumens e o Método Ponto a Ponto. A luz visível está contida no espectro da radiação térmica e, portanto, o fluxo luminoso pode ser relacionado ao fluxo de radiação térmica. Determinar as posições e as competências das fontes de luz necessárias na superfície de projeto ganha importância quando o comportamento, em termos de uniformidade ou de fluxo radiante, é especificado. O presente trabalho visa a estabelecer diferentes valores de fluxo em duas regiões distintas da superfície do projeto. Por meio do posicionamento das fontes de luz, é estabelecido um fluxo maior na região denominada principal e um fluxo menor na região denominada secundária. A modelagem matemática da radiação térmica (Método das Radiosidades) é aplicada ao projeto de iluminação, considerando-se as características da visão humana e o comportamento das fontes de luz. Na modelagem, é considerada uma cavidade retangular tridimensional com superfícies cinza e com condição de parede fria, na qual o poder emissivo das paredes é nulo. As fontes de luz são representadas por unidades de malha no teto. A relação de equações é resolvida por metodologia inversa, usando o algoritmo de Otimização Extrema Generalizada (GEO). Este algoritmo é classificado como um método de otimização estocástica de busca global para a resolução de sistemas considerados inicialmente mal condicionados. A posição e a potência das fontes luminosas são determinadas pela resolução do sistema de equações, de forma a proporcionar um fluxo de radiação duas vezes maior na região principal em relação à região secundária. A função objetivo do processo consiste em minimizar a diferença entre o fluxo desejado e os valores de fluxo de radiação incidente nas duas regiões da superfície de projeto. Em virtude das características de simetria do problema, a relação é estabelecida para apenas um quarto da cavidade. Assim, por exemplo, aplicar a metodologia com 9 fontes de luz a um quarto da região resulta em 36 fontes de luz em toda a cavidade. Os resultados mostram que é possível encontrar um arranjo de fontes de luz preestabelecendo-se duas condições de potência. / In the development of environmental illumination projects, one of the main goals to be achieved is the visual comfort, which is usually done by known methodologies, like the Lumens Method and the Point by Point Method. Since the visible light is contained in the spectrum of thermal radiation, the luminous flux can be related to the thermal radiation flux. The determination of the position and power of the light sources required by the design surface gains an higher importance whenever a behavior is specified, should it be in terms of uniformity or in therms of radiant flux. In this work, we describe a method that allows the establishment of different flux values in two distinct regions of the design surface, which are referred by the names main region and secondary region. Through the spatial arrangement of the light sources, the method sets a more intense flux in the main region and a less intense one in the secondary region. The mathematical model of thermal radiation, known as Radiosity Method, is applied to the illumination design, along with the characteristics of the human vision and the behavior of light sources. In this model, a rectangular three-dimensional cavity is considered. It has gray surfaces and exhibits the conditions of a cold wall, in which the emissivity power of the walls is null. The light sources are represented by a mesh unit in the ceiling. The system of equations is solved by inversemethodology, using the Generalized Extremal Optimization (GEO) algorithm. This algoritm is classified as being a stochastic optimization method of global search to solve systems that are initially considered ill-conditioned. By solving this system, the position and power of light sources can be determined, and this is done in such a way that the flux radiation in the main region is twice more intense then the one in the secondary region. The target function of the whole process is to minimize the difference between the desired flux and the incident flux radiation values for each one of the two design surface regions. We further explore the problem symmetry, solving the equation system for only a quarter of the cavity. This way, if the methodology is applied with nine light sources into a quarter of the region, the entire cavity will behave as if it has 36 light sources. Our results show that, given two prescribed conditions of power, it is possible to find an arrangement of light sources.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

A utilização de redes complexas para a descriçãoi de diversos sistemas naturais e artificias,compreendidos nas mais diversas áreas do conhecimento humano, tem se mostrado uma abordagem poderosa para a redução da complexidade inerente a tais sistemas. Em muitos casos, tal complexidade resulta do número de componentes envolvidos e de suas intrincadas relações. Uma forma de reduzir a complexidade associada a tais sistemas, consiste em identificar e agrupar componentes que possuam características similares. Sendo assim, desenvolvemos nesta tese métodos de identificação de comunidades em redes complexas. Tais métodos se baseiam na ideia de que comunidades surgem quando grupos de vértices possuem um número mais elevado de conexões entre os vértices do mesmo grupo do que com vértices externos à este grupo. Além disso, utilizamos a função modularidade como função objetivo e como forma de avaliação e comparação dos resultados obtidos nesta tese com resultados previamente reportados na literatura. Uma vez estabelecido um método de identificação de comunidades, utilizamos a abordagem de redes complexas para a determinação de domínios estruturais de proteínas. Para tal, criamos redes de contato entre os aminoácidos de uma proteí?na buscando representar apenas as ligações relevantes do ponto de vista topológico. Por meio destas representações, aplicamos os métodos de identificação de comunidades desenvolvidos nesta tese, no intuito de identificar domínios estruturais de cadeias proteicas. Por fim, desenvolvemos um método específico para a identificação de domínios em proteínas com dois domínios sequencias, concluindo desta forma, os objetivos propostos nesta tese. / The use of complex networks for the representation of various natural and artificial sys- tems in the most diverse fields of human knowledge, has proven to be a powerful approach for the reduction of the complexity in the study of such systems. In many cases, this complexity emerges from the number of components of the system and from the intricate relationship between them. A reduction in this complexity is made possible by the iden- tification and grouping of the components of the system with similar characteristics. In this way, we developed in this thesis, methods for community identification in complex networks. Such methods are based on the notion that communities arise when groups of vertices are more densely connected with vertices of their same group, than with ver- tices belonging to other groups in the network. Moreover, the modularity function has been used as an objective function, and as a score for the evaluation and comparison of the results obtained in this thesis with the results reported in the literature of complex networks. Upon the establishment of a method for community detection, we used the framework of complex networks to the determination of structural protein domains. The- refore, we have created contact networks of amino acids of protein chains, focusing on the representation of only the most relevant interactions between them, from a topological point of view. We have applied to these networks the methods for community identi- fication developed in this thesis, aiming to identify the structural domains of proteins. Finally, we have developed a specific method for the identification of protein domains in protein chains with two sequential domains, concluding in this way, the objectives proposed in this thesis.