To see the other types of publications on this topic, follow the link: Erdős.
Dissertations / Theses on the topic 'Erdős'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Erdős.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Heinlein, Matthias [Verfasser]. "Erdős-Pósa properties / Matthias Heinlein." Ulm : Universität Ulm, 2019. http://d-nb.info/1177147033/34.
Full text
2
Bedich, Joseph Matthew. "An Introduction to the Happy Ending Problem and the Erdős–Szekeres Conjecture." The Ohio State University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=osu152405396768852.
Full text
3
Rupert, Malcolm. "Extending Erdős-Kac and Selberg-Sathe to Beurling primes with controlled integer counting functions." Thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/44300.
Full textAbstract:
In this thesis we extend two important theorems in analytic prime number theory to a the setting of Beurling primes, namely The Erdős–Kac theorem and a theorem of Sathe and Selberg. The Erdős–Kac theorem
asserts that the number of prime factors that divide an integer n is, in some sense, normally distributed with mean log log n and variance
log log n. Sathe proved and Selberg substantially refined a formula for the counting function of products of k primes with some uniformity on k. A set of Beurling primes is any countable multiset of the reals with elements that tend towards infinity. The set of Beurling primes has a corresponding multiset of Beurling integers formed by all finite products of Beurling primes. We assume that the Beurling integer counting function is approximately linear with varying conditions on the error term in order to prove the stated results. An interesting example of a set of Beurling primes is the set of norms of prime ideals of the ring of integers of a number field. Recently, Granville and Soundararajan have developed a particularly simple proof of the Erdős–Kac theorem which we follow in this thesis. For extending the theorem of Selberg and Sathe much more analytic machinery is needed.
4
Boggess, Michael H. "Four Years with Russell, Gödel, and Erdős: An Undergraduate's Reflection on His Mathematical Education." Scholarship @ Claremont, 2017. http://scholarship.claremont.edu/cmc_theses/1669.
Full textAbstract:
Senior Thesis at CMC is often described institutionally as the capstone of one’s undergraduate education. As such, I wanted my own to accurately capture and reflect how I’ve grown as a student and mathematician these past four years. What follows is my attempt to distill lessons I learned in mathematics outside the curriculum, written for incoming undergraduates and anyone with just a little bit of mathematical curiosity. In it, I attempt to dispel some common preconceptions about mathematics, namely that it’s uninteresting, formulaic, acultural, or completely objective, in favor of a dynamic historical and cultural perspective, with particular attention paid to the early twentieth century search to secure the foundations of mathematics and a detailed look at contemporary Hungarian mathematics. After doing so, I conclude that the scope of mathematics is not what one might expect but that it’s still absolutely worth doing and appreciating.
5
McLaughlin, Bryce. "An Incidence Approach to the Distinct Distances Problem." Scholarship @ Claremont, 2018. https://scholarship.claremont.edu/hmc_theses/118.
Full textAbstract:
In 1946, Erdös posed the distinct distances problem, which asks for the minimum number of distinct distances that any set of n points in the real plane must realize. Erdös showed that any point set must realize at least &Omega(n1/2) distances, but could only provide a construction which offered &Omega(n/&radic(log(n)))$ distances. He conjectured that the actual minimum number of distances was &Omega(n1-&epsilon) for any &epsilon > 0, but that sublinear constructions were possible. This lower bound has been improved over the years, but Erdös' conjecture seemed to hold until in 2010 Larry Guth and Nets Hawk Katz used an incidence theory approach to show any point set must realize at least &Omega(n/log(n)) distances. In this thesis we will explore how incidence theory played a roll in this process and expand upon recent work by Adam Sheffer and Cosmin Pohoata, using geometric incidences to achieve bounds on the bipartite variant of this problem. A consequence of our extensions on their work is that the theoretical upper bound on the original distinct distances problem of &Omega(n/&radic(log(n))) holds for any point set which is structured such that half of the n points lies on an algebraic curve of arbitrary degree.
6
Nan, Yehong. "Empirical Study of Two Hypothesis Test Methods for Community Structure in Networks." Thesis, North Dakota State University, 2019. https://hdl.handle.net/10365/31640.
Full textAbstract:
Many real-world network data can be formulated as graphs, where a binary relation exists between nodes. One of the fundamental problems in network data analysis is community detection, clustering the nodes into different groups. Statistically, this problem can be formulated as hypothesis testing: under the null hypothesis, there is no community structure, while under the alternative hypothesis, community structure exists. One is of the method is to use the largest eigenvalues of the scaled adjacency matrix proposed by Bickel and Sarkar (2016), which works for dense graph. Another one is the subgraph counting method proposed by Gao and Lafferty (2017a), valid for sparse network. In this paper, firstly, we empirically study the BS or GL methods to see whether either of them works for moderately sparse network; secondly, we propose a subsampling method to reduce the computation of the BS method and run simulations to evaluate the performance.
7
Raouj, Abdelaziz. "Sur la densité de certains ensembles de multiples : résolution d'une conjecture d'Erdös." Nancy 1, 1992. http://docnum.univ-lorraine.fr/public/SCD_T_1992_0120_RAOUJ.pdf.
Full textAbstract:
Erdös a conjecturé que, lorsque l'entier n parcourt une suite convenable de densité unité presque chaque entier M possède un diviseur proche d'un diviseur de N. Nous résolvons cette conjecture sous une forme quantitative et plus générale, en évaluant asymptotiquement la densité de certains ensembles de multiples définis a partir de l'ensemble des diviseurs de N. Les démonstrations reposent sur la technique de Maier et Tenenbaum, et sur des calculs de moyennes pondérées, étayées par des raisonnements combinatoires. Certaines propriétés de nature probabiliste sont établies par des méthodes d'analyse harmonique.
8
Stef, André. "L'ensemble exceptionnel dans la conjecture d'Erdös concernant la proximité des diviseurs." Nancy 1, 1992. http://docnum.univ-lorraine.fr/public/SCD_T_1992_0130_STEF.pdf.
Full textAbstract:
P. Erdös conjectura dans les années trente que presque tout entier possède deux diviseurs distincts dont le rapport est compris entre un et deux. Maier et Tenenbaum démontrèrent ce résultat en 1983. Dans un premier temps, nous donnons un encadrement du nombre des entiers inferieurs à x ne vérifiant pas la propriété. La majoration s'obtient en affinant la démonstration de Maier et Tenenbaum. La minoration s'obtient en considérant les entiers ayant peu de facteurs premiers. Nous considérons ensuite, dans un travail commun avec Gérald Tenenbaum, les entiers, dits lexicographiques, pour lesquels l'ordre lexicographique (ou multiplicatif) sur les diviseurs correspond à l'ordre naturel (ou additif). Nous estimons le comportement asymptotique de la fonction de compte de ces entiers. Nous en déduisons notamment une minoration de la fonction de compte des entiers ne vérifiant pas la conjecture d'Erdös et possédant un nombre normal de facteurs premiers.
9
Corre, Pierre-Antoine. "Processus de branchements et graphe d'Erdős-Rényi." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066409/document.
Full textAbstract:
Le fil conducteur de cette thèse, composée de trois parties, est la notion de branchement.Le premier chapitre est consacré à l'arbre de Yule et à l'arbre binaire de recherche. Nous obtenons des résultats d'oscillations asymptotiques de l'espérance, de la variance et de la distribution de la hauteur de ces arbres, confirmant ainsi une conjecture de Drmota. Par ailleurs, l'arbre de Yule pouvant être vu comme une marche aléatoire branchante évoluant sur un réseau, nos résultats permettent de mieux comprendre ce genre de processus.Dans le second chapitre, nous étudions le nombre de particules tuées en 0 d'un mouvement brownien branchant avec dérive surcritique conditionné à s'éteindre. Nous ferons enfin apparaître une nouvelle phase de transition pour la queue de distribution de ces variables.L'objet du dernier chapitre est le graphe d'Erdős–Rényi dans le cas critique : $G(n,1/n)$. En introduisant un couplage et un changement d'échelle, nous montrerons que, lorsque $n$ augmente les composantes de ce graphe évoluent asymptotiquement selon un processus de coalescence-fragmentation qui agit sur des graphes réels. La partie coalescence sera de type multiplicatif et les fragmentations se produiront selon un processus ponctuel de Poisson sur ces objetsThis thesis is composed by three chapters and its main theme is branching processes.The first chapter is devoted to the study of the Yule tree and the binary search tree. We obtain oscillation results on the expectation, the variance and the distribution of the height of these trees and confirm a Drmota's conjecture. Moreover, the Yule tree can be seen as a particular instance of lattice branching random walk, our results thus allow a better understanding of these processes.In the second chapter, we study the number of particles killed at 0 for a Brownian motion with supercritical drift conditioned to extinction. We finally highlight a new phase transition in terms of the drift for the tail of the distributions of these variables.The main object of the last chapter is the Erdős–Rényi graph in the critical case: $G(n,1/n)$. By using coupling and scaling, we show that, when $n$ grows, the scaling process is asymptotically a coalescence-fragmentation process which acts on real graphs. The coalescent part is of multiplicative type and the fragmentations happen according a certain Poisson point process
10
Gauy, Marcelo Matheus. "Erdos-Ko-Rado em famílias aleatórias." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-26082014-095951/.
Full textAbstract:
Estudamos o problema de famílias intersectantes extremais em um subconjunto aleatório da família dos subconjuntos com exatamente k elementos de um conjunto dado. Obtivemos uma descrição quase completa da evolução do tamanho de tais famílias. Versões semelhantes do problema foram estudadas por Balogh, Bohman e Mubayi em 2009, e por Hamm e Kahn, e Balogh, Das, Delcourt, Liu e Sharifzadeh de maneira concorrente a este trabalho.We studied the problem of maximal intersecting families in a random subset of the family of subsets with exactly k elements from a given set. We obtained a nearly complete description of the evolution of the size of such families. Similar versions of this problem have been studied by Balogh, Bohman and Mubayi in 2009, and by Hamm and Kahn, and Balogh, Das, Delcourt, Liu and Sharifzadeh concurrently with this work.
11
VASCONCELOS, José Eder Salvador de. "A Propriedade Erdös-Pósa para matróides." Universidade Federal de Campina Grande, 2009. http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/1217.
Full textAbstract:
Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-23T15:16:49Z
No. of bitstreams: 1
JOSÉ EDER SALVADOR DE VASCONCELOS - DISSERTAÇÃO PPGMAT 2009..pdf: 634118 bytes, checksum: e65e70c702364b197a36f09e8d1ef296 (MD5)Made available in DSpace on 2018-07-23T15:16:49Z (GMT). No. of bitstreams: 1 JOSÉ EDER SALVADOR DE VASCONCELOS - DISSERTAÇÃO PPGMAT 2009..pdf: 634118 bytes, checksum: e65e70c702364b197a36f09e8d1ef296 (MD5) Previous issue date: 2009-11
Capes
O número de cocircuitos disjuntos em uma matróide é delimitado pelo seu posto. Existem, no entanto, matróides de posto arbitrariamente grande que não contêm dois cocircuitos disjuntos. Considere, por exemplo,M(Kn) eUn,2n. Além disso, a matróide bicircularB(Kn) pode ter posto arbitrariamente grande, mas não tem 3 cocircuitos disjuntos. Nós apresentaremos uma prova, obtida por Jim Geelen e Kasper Kabell em (5), para o seguinte fato: para cadak en, existe uma constantec tal que, seM é uma matróide com posto no mínimoc, entãoM temk cocircuitos disjuntos ou contém uma das seguintes matróides como menorUn,2n,M(Kn) ouB(Kn).
The number of disjoint cocircuits in a matroid is bounded by its rank. There are, however, matroids of rank arbitrarily large that do not contain two disjoint cocircuits. Consider, for example,M(kn) andUn,2n. Moreover, the bicircular matroidB(kn) may have arbitrarily large rank but do not have 3 disjoints cocircuits. We show a proof obtained by Jim Geelen and Kasper Kabell in (5) to the following fact: for everyk andn, there is a constantc such that ifM is a matroid with rank at leastc, thenM hask disjoint cocircuits orM contains one of the following matroids as a minorUn,2n, M(kn) orB(kn).
12
Santos, Sidneia Silveira. "Apresentações do Teorema de Erdos-Mordell." Instituto de Matemática. Departamento de Matemática, 2015. http://repositorio.ufba.br/ri/handle/ri/23023.
Full textAbstract:
Submitted by Marcos Samuel (msamjunior@gmail.com) on 2017-06-09T14:07:57Z
No. of bitstreams: 1
DissertaçãoSideneia.pdf: 2505985 bytes, checksum: 58af908982530da682fb1e186eae51c4 (MD5)Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-06-16T14:47:15Z (GMT) No. of bitstreams: 1 DissertaçãoSideneia.pdf: 2505985 bytes, checksum: 58af908982530da682fb1e186eae51c4 (MD5)
Made available in DSpace on 2017-06-16T14:47:15Z (GMT). No. of bitstreams: 1 DissertaçãoSideneia.pdf: 2505985 bytes, checksum: 58af908982530da682fb1e186eae51c4 (MD5)
O teorema de Erdos-Mordell além de ser muito interessante, apresenta muitas demonstrações diferentes, boa parte delas envolvendo conte udos estudados na Educação Básica. Se tais demonstrações forem abordadas nestas séries, além de despertar a curiosidade dos alunos, daria ao professor a possibilidade de utilizando um material concreto, tornar suas aulas mais dinâmicas, envolvendo os alunos e ao mesmo tempo despertando um maior interesse da parte deles.Tendo como objetivo, mostrar ao professor algumas possibilidades de apresentar aos alunos da Educação Básica o teorema de Erdos-Mordell, este trabalho trás algumas propostas pedagógicas envolvendo este teorema, utilizando o material concreto, afim de, como dito anteriormente, dinamizar as aulas, aguçando a curiosidade e despertando o interesse do aluno.
13
Vesely, Anna. "Grafi aleatori - il modello di Erdos-Rényi." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amslaurea.unibo.it/10144/.
Full textAbstract:
Dopo aver dato una definizione formale per il modello di Erdos-Rényi, si dimostra che in un grafo ER il grado dei nodi (misura della connessione) risulta essere una variabile aleatoria con distribuzione binomiale, mentre il clustering (misura della densità di archi a livello locale) tende a zero. Successivamente si determinano le funzioni soglia per alcune proprietà monotone particolarmente significative, consentendo così di descrivere diverse configurazioni possibili per un grafo ER al variare dei suoi parametri. Infine, si mostra come si possano utilizzare i grafi ER per modellizzare la diffusione di una malattia infettiva all’interno di una popolazione numerosa.
14
Oliveira, Filipe Augusto Alves de. "Teorema de Erdös-Ginzburg-Ziv com Peso." Universidade Federal de Viçosa, 2014. http://locus.ufv.br/handle/123456789/4929.
Full textAbstract:
Made available in DSpace on 2015-03-26T13:45:36Z (GMT). No. of bitstreams: 1
texto completo.pdf: 532124 bytes, checksum: 0e9370c9afd85879f731f2f34fc05c51 (MD5)
Previous issue date: 2014-02-17Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
In this work we present generalizations to a famous result of the Additive Number Theory which is the Erdös-Ginzburg-Ziv theorem. Our first goal is to find the lowest value for o the length of a sequence of integers for which we can always find a subsequence of n terms which, together with weight in {1, −1}, assume a value equal to a multiple of n. We also consider one generalizations to Erdös-Ginzburg-Ziv theorem where the sequences are o formed by elements in a finite abelian group and for which we can, under some conditions, atribute any weight on the sums of elements of the sequence.
Neste trabalho apresentaremos generalizações para um famoso resultado da Teoria Aditiva dos Números que é o Teorema de Erdös-Ginzburg-Ziv. Nosso primeiro objetivo é encontrar o menor valor para o comprimento de uma sequência de inteiros em que sempre podemos encontrar uma subsequência de n termos que, somados com pesos em {1, −1}, assumam e um valor igual a um múltiplo de n. Posteriormente, consideraremos uma generalização para o Teorema de Erdös-Ginzburg-Ziv em que as sequências são formadas de elementos em um grupo abeliano finito qualquer e que podemos, sob algumas condições, colocar pesos quaisquer sobre as somas dos elementos da sequência.
15
Cruz, Diogo Filipe Pessoa da. "A conjetura de Erdös-Straus e generalizações." Master's thesis, Universidade de Aveiro, 2013. http://hdl.handle.net/10773/13324.
Full textAbstract:
Mestrado em Matemática e Aplicações - Ciências da ComputaçãoNesta dissertação serão apresentados os principais resultados relacionados com a conjetura de Erd}os-Straus, entre os quais o teorema de Mordell. Associada à conjetura está uma equação diofantina, que iguala uma fração de numerador n = 4 e denominador m inteiro maior que 1, à soma de três frações unitárias. Será também analisado o número de soluções desta equação e vamos também verificar computacionalmente a validade da conjetura para m _ 109. Finalmente, iremos ver generalizações da conjetura para qualquer n e para quando, para além de somas, podemos também ter subtrações de frações unitárias. Ambas as generalizações foram propostas por André Schinzel.
This dissertation will present the main results related to the Erd}os- Straus conjecture, including the Mordell's theorem. Associated to the conjecture is a diophantine equation, that say that a fraction with numerator n = 4 and denominator m integer greater than 1 is equal to the sum of three unit fractions. It will be also analyzed the number of solutions of this equation and we also computationally verify the validity of the conjecture for m 109. Finally, we will see generalizations of the conjecture for any n and when, in addition to sums, we also have subtractions of unit fractions. Both generalizations were proposed by Andr é Schinzel.
This dissertation will present the main results related to the Erd}os- Straus conjecture, including the Mordell's theorem. Associated to the conjecture is a diophantine equation, that say that a fraction with numerator n = 4 and denominator m integer greater than 1 is equal to the sum of three unit fractions. It will be also analyzed the number of solutions of this equation and we also computationally verify the validity of the conjecture for m _ 109. Finally, we will see generalizations of the conjecture for any n and when, in addition to sums, we also have subtractions of unit fractions. Both generalizations were proposed by André Schinzel.
16
Hamilton, Jeremy. "An Exploration of the Erdös-Mordell Inequality." Youngstown State University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=ysu1287605197.
Full text
17
Saidak, F. "Non-Abelian generalizations of the Erdös-Kac theorem." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ63451.pdf.
Full text
18
Silva, Everton Juliano da. "Uma demonstração analítica do teorema de Erdös-Kac." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/45/45131/tde-24032015-132813/.
Full textAbstract:
Em teoria dos números, o teorema de Erdös-Kac, também conhecido como o teorema fundamental de teoria probabilística dos números, diz que se w(n) denota a quantidade de fatores primos distintos de n, então a sequência de funções de distribuições N definidas por FN(x) = (1/N) #{n <= N : (w(n) log log N)/(log log N)^(1/2)} <= x}, converge uniformemente sobre R para a distribuição normal padrão. Neste trabalho desenvolvemos todos os teoremas necessários para uma demonstração analítica, que nos permitirá encontrar a ordem de erro da convergência acima.In number theory, the Erdös-Kac theorem, also known as the fundamental theorem of probabilistic number theory, states that if w(n) is the number of distinct prime factors of n, then the sequence of distribution functions N, defined by FN(x) = (1/N) #{n <= N : (w(n) log log N)/(log log N)^(1/2)} <= x}, converges uniformly on R to the standard normal distribution. In this work we developed all theorems needed to an analytic demonstration, which will allow us to find an order of error of the above convergence.
19
Goudout, Elie. "Étude de la fonction ω : petits intervalles et systèmes translatés." Thesis, Sorbonne Paris Cité, 2019. http://www.theses.fr/2019USPCC040.
Full textAbstract:
Dans cette thèse, on s’intéresse à l’interaction entre les structures multiplicative et additive des entiers. Pour cela, on étudie notamment la fonction « nombre de facteurs premiers distincts », notée ω, dans de très petits intervalles, mais aussi sur des systèmes translatés. Ce projet est né suite à une importante percée de Matomäki & Radziwiłł dans l’étude des petits intervalles, en 2015. Dans un premier temps, on démontre que le théorème d’Erdős-Kac est vérifié dans presque tous les petits intervalles, dès lors que leur taille tend vers l’infini. On s’intéresse ensuite aux lois locales de la fonction ω. On parvient à démontrer, lorsque , que presque tous les intervalles de longueur h contiennent des entiers n6x vérifiant ω(n) = k, dès que h est suffisamment grand. Lorsque , la condition sur h est optimale. On obtient un résultat analogue, bien que non optimal, sur les entiers x1/u-friables pour u6 (logx)1/6−ε, où ε> 0 peut être fixé arbitrairement petit. Les méthodes employées dans le deuxième chapitre invitent naturellement à étudier le comportement de certaines fonctions additives sur des systèmes d’entiers translatés. On démontre alors, dans un troisième temps, une version multidimensionnelle d’un théorème de 1975 dû à Halász, relatif à la concentration maximale des valeurs d’une seule fonction additive. Enfin, dans le quatrième chapitre, on démontre que ω(n−1) vérifie un théorème d’ErdősKac lorsque ω(n) = k est fixé. Cela généralise un résultat d’HalberstamIn this thesis, we study the interactions between the multiplicative and additive structures of integers. As such, we particularly investigate the function “number of distinct prime factors”, noted ω, on short intervals and shifted systems. This project originates from an important breakthrough of Matomäki & Radziwiłł regarding the study of small intervals, in 2015. As a first step, we show that the Erdős-Kac theorem is valid in almost all short intervals, as long as their length goes to infinity. We then consider the local laws of ω. We prove that, for x> 3 and , almost all intervals of length h contain integers n 6 x satisfying ω(n) = k, when h is large enough. For , the condition on h is optimal. A similar result, albeit non optimal, is obtained for x1/u-friable integers with u 6 (logx)1/6−ε, where ε > 0 is fixed, arbitrarily small. The techniques used in the second chapter naturally invite us to consider the behavior of a wide class of additive functions on shifted systems. In the third chapter, we prove a multidimensional version of a theorem from Halász in 1975, regarding the maximum concentration of the values of one additive function. In the last chapter, we show that ω(n− 1) satisfies an Erdős-Kac theorem whenever ω(n) = k is fixed. This generalizes a theorem of Halberstam
20
Lima, Carlos Vinicius Gomes Costa. "Sobre b-coloraÃÃo de grafos com cintura pelo menos 6." Universidade Federal do CearÃ, 2013. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=9630.
Full textAbstract:
Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgicoThe coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-LovÂasz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set.
O problema de coloraÃÃo està entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teorica e prÃtica. Dado que o problema de colorir os vÃrtices de um grafo G qualquer com a menor quantidade de cores à NP-difÃcil, vÃrias heurÃsticas de coloraÃÃo sÃo estudadas a fim de obter uma coloraÃÃo prÃpria com um nÃmero de cores razoavelmente pequeno. Dado um grafo G, a heurÃstica b de coloraÃÃo se resume a diminuir a quantidade de cores utilizadas em uma coloraÃÃo prÃpria c, de modo que, se todos os vÃrtices de uma classe de cor deixam de ver alguma cor em sua vizinhanÃa, entÃo podemos modificar a cor desses vÃrtices para qualquer cor inexistente em sua vizinhanÃa. Dessa forma, obtemos uma coloraÃÃo c′ com uma cor a menos que c. Irving e Molove definiram a b-coloraÃÃo de um grafo G como uma coloraÃÃo onde toda classe de cor possui um vÃrtice que à adjacente as demais classes de cor. Esses vÃrtices sÃo chamados b-vÃrtices. Irving e Molove tambÃm definiram o nÃmero b-cromÃtico como o maior inteiro k tal que G admite uma b-coloraÃÃo por k cores. Eles mostraram que determinar o nÃmero b-cromÃtico de um grafo qualquer à um problema NP-difÃcil, mas polinomial para Ãrvores. Irving e Molove tambÃm definiram o m-grau de um grafo, que à o maior inteiro m(G) tal que existem m(G) vÃrtices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau à um limite superior para nÃmero b-cromÃtico e mostraram que o mesmo à igual a m(T) ou a m(T)−1, para toda Ãrvore T, onde o nÃmero b-cromÃtico à igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertaÃÃo, verificamos a relaÃÃo entre a cintura, que à o tamanho do menor ciclo, e o nÃmero b-cromÃtico de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G à pelo menos g∗, entÃo o nÃmero b-cromÃtico à igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ à no mÃximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de ErdÃs-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ à 9. Caracterizamos os grafos cuja cintura à pelo menos 6 e nÃo possuem um conjunto bom e mostramos como b-colori-los de forma Ãtima. AlÃm disso, mostramos como bicolorir, tambÃm de forma Ãtima, os grafos cuja cintura à pelo menos 7 e nÃo possuem conjunto bom.
21
Lopes, Fabio Marcellus Lima Sá Makiyama. "Limite do fluído para o grafo aleatório de Erdos-Rényi." Universidade de São Paulo, 2010. http://www.teses.usp.br/teses/disponiveis/45/45133/tde-05052010-155151/.
Full textAbstract:
Neste trabalho, aplicamos o algoritmo Breadth-First Search para encontrar o tamanho de uma componente conectada no grafo aleatório de Erdos-Rényi. Uma cadeia de Markov é obtida deste procedimento. Apresentamos alguns resultados bem conhecidos sobre o comportamento dessa cadeia de Markov. Combinamos alguns destes resultados para obter uma proposição sobre a probabilidade da componente atingir um determinado tamanho e um resultado de convergência do estado da cadeia neste instante. Posteriormente, aplicamos o teorema de convergência de Darling (2002) a sequência de cadeias de Markov reescaladas e indexadas por N, o número de vértices do grafo, para mostrar que as trajetórias dessas cadeias convergem uniformemente em probabilidade para a solução de uma equação diferencial ordinária. Deste resultado segue a bem conhecida lei fraca dos grandes números para a componente gigante do grafo aleatório de Erdos-Rényi, no caso supercrítico. Além disso, obtemos o limite do fluído para um modelo epidêmico que é uma extensão daquele proposto em Kurtz et al. (2008).In this work, we apply the Breadth-First Search algorithm to find the size of a connected component of the Erdos-Rényi random graph. A Markov chain is obtained of this procedure. We present some well-known results about the behavior of this Markov chain, and combine some of these results to obtain a proposition about the probability that the component reaches a certain size and a convergence result about the state of the chain at that time. Next, we apply the convergence theorem of Darling (2002) to the sequence of rescaled Markov chains indexed by N, the number of vertices of the graph, to show that the trajectories of these chains converge uniformly in probability to the solution of an ordinary dierential equation. From the latter result follows the well-known weak law of large numbers of the giant component of the Erdos-Renyi random graph, in the supercritical case. Moreover, we obtain the uid limit for an epidemic model which is an extension of that proposed in Kurtz et al. (2008).
22
Louani, Djamal. "Lois limites du type erdos-renyi indexees par des ensembles." Paris 6, 1990. http://www.theses.fr/1990PA066758.
Full textAbstract:
En introduction de cette these, nous donnons dans la premiere partie un expose sur la notion d'entropie et ses applications dans la theorie des processus aleatoires ainsi qu'un certain nombre de resultats. Dans la deuxieme partie, nous donnons un expose complet sur la statistique d'erdos-renyi et ses extensions avec un rappel d'un certain nombre de resultats de grandes deviations. Dans la deuxieme partie, nous etablissons des lois du type erdos-renyi pour des sommes de variables aleatoires indexees par des sous-ensembles d'un ensemble discret i quand un certain nombre d'hypotheses d'entropie et de capacite sont verifiees. Nous examinons, en particulier, le cas ou i est l'ensemble des entiers naturels ainsi que le cas de variables aleatoires normalement distribuees. L'etude des processus des quantiles est faite au chapitre 3, celle des processus de poisson homogenes spaciaux est donnee au chapitre 4. La derniere partie de cette these est consacree a l'etude des processus empiriques dans le cas d'erdos-renyi et dans le cas d'erdos-renyi degenere avec une application au processus de poisson
23
Gardes, Marie-Line. "Étude de processus de recherche de chercheurs, élèves et étudiants, engagés dans la recherche d’un problème non résolu en théorie des nombres." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10231/document.
Full textAbstract:
A l’articulation de la théorie des nombres et de la didactique des mathématiques, notre recherche vise à étudier la question de la transposition du travail du mathématicien, via l’analyse de processus de recherche de chercheurs, élèves et étudiants sur la recherche d’un même problème non résolu : la conjecture d’Erdös-Straus. Les analyses mathématiques et épistémologiques nous ont permis d’identifier différents aspects du travail du mathématicien et les éléments moteurs dans l’avancée de ses recherches. Cela nous a conduit à développer la notion de « geste » de la recherche pour décrire, analyser et mettre en perspective les processus de recherche des trois publics. Ces analyses ont mis en évidence les potentialités du problème pour créer une situation de recherche de problèmes en classe, plaçant les élèves dans une position proche de celle du mathématicien. Les analyses didactiques se sont appuyées sur la construction d’une telle situation puis sur sa mise à l’épreuve dans un contexte de laboratoire avec des élèves de terminale scientifique. Nous avons analysé finement les processus de recherche des élèves à l’aide des outils méthodologiques développés dans les analyses mathématiques et épistémologiques. Les analyses ont mis en évidence la richesse des procédures mises en oeuvre, un travail effectif dela dialectique entre les connaissances mathématiques et les heuristiques mobilisées, et selonles groupes, une mise en oeuvre de démarches de type expérimental, l’approfondissement de connaissances mathématiques notionnelles et une acquisition d’heuristiques expertes de recherche de problème non résolu. Elles montrent également la pertinence de la notion de «geste » de la recherche pour étudier la question de la transposition du travail des chercheursOur thesis deals with the transposition of mathematician’s reserach activity in mathematical classroom, in the domain of number theory. Our research focuses on the study of a research process for researchers, pupils and students involved in the research of an unsolved problem: the Erdös-Straus conjecture. Our mathematical and epistemological analyses allow us to identify different aspects of the mathematician’s work and the elements for progress in his research. The notion of “gesture” is developed to describe, analyze and contextualize different research processes. This analysis reveals the potentiality of this problem to create a research situation in classroom, where pupils are in a position similar to the mathematician’s one. Didactical analyses are based on the construction of such a situation and its experimentation in laboratory. We study the research process of the students with the methodological tools developed in mathematical and epistemological analyses. This analysis shows several potentiality of this situation: a wealth of procedures implemented, effective work on the dialectical aspects of the mathematical research activity and implementation of experimental approach. The notion of “gesture” is relevant to consider the question of the transposition of mathematician’s work
24
Lima, Carlos Vinicius Gomes Costa. "Sobre b-coloração de grafos com cintura pelo menos 6." reponame:Repositório Institucional da UFC, 2013. http://www.repositorio.ufc.br/handle/riufc/17634.
Full textAbstract:
LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 59 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza- Ceará, 2013.Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T18:53:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5)
Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T19:18:47Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5)
Made available in DSpace on 2016-06-13T19:18:47Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013
O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom.
The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set.
25
Alberici, Diego. "Statistical Mechanics of Monomer-Dimer Models on Complete and Erdös-Rényi Graphs." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2012. http://amslaurea.unibo.it/4169/.
Full textAbstract:
Nella tesi sono trattate due famiglie di modelli meccanico statistici su vari grafi: i modelli di spin ferromagnetici (o di Ising) e i modelli di monomero-dimero.
Il primo capitolo è dedicato principalmente allo studio del lavoro di Dembo e Montanari, in cui viene risolto il modello di Ising su grafi aleatori.
Nel secondo capitolo vengono studiati i modelli di monomero-dimero, a partire dal lavoro di Heilemann e Lieb,con l'intento di dare contributi nuovi alla teoria. I principali temi trattati sono disuguaglianze di correlazione, soluzioni esatte su alcuni grafi ad albero e sul grafo completo, la concentrazione dell'energia libera intorno al proprio valor medio sul grafo aleatorio diluito di Erdös-Rényi.
26
Bedia, Elizbeth Chipa. "Conectividade do grafo aleatório de Erdös-Rényi e uma variante com conexões locais." Universidade Federal de São Carlos, 2016. https://repositorio.ufscar.br/handle/ufscar/7493.
Full textAbstract:
Submitted by Regina Correa (rehecorrea@gmail.com) on 2016-09-26T13:07:54Z
No. of bitstreams: 1
DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5)Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-27T19:24:19Z (GMT) No. of bitstreams: 1 DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5)
Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-27T19:24:24Z (GMT) No. of bitstreams: 1 DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5)
Made available in DSpace on 2016-09-27T19:24:30Z (GMT). No. of bitstreams: 1 DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5) Previous issue date: 2016-03-24
Não recebi financiamento
We say that a graph is connected if there is a path edges between any pair of vertices. Random graph Erd os-R enyi with n vertices is obtained by connecting each pair of vertex with probability pn 2 (0; 1) independently of the others. In this work, we studied in detail the connectivity threshold in the connection probability pn for random graphs Erd os-R enyi when the number of vertices n diverges. For this study, we review some basic probabilistic tools (convergence of random variables and methods of the rst and second moment), which will lead to a better understanding of more complex results. In addition, we apply the above concepts for a model with a simple topology, speci cally studied the asymptotic behavior of the probability of non-existence of isolated vertices, and we discussed the connectivity or not of the graph. Finally we show the convergence in distribution of the number of isolated vertices for a Poisson distribution of the studied model.
Dizemos que um grafo e conectado se existe um caminho de arestas entre quaisquer par de vértices. O grafo aleatório de Erd os-R enyi com n vértices e obtido conectando cada par de vértice com probabilidade pn 2 (0; 1), independentemente dos outros. Neste trabalho, estudamos em detalhe o limiar da conectividade na probabilidade de conexão pn para grafos aleat órios Erd os-R enyi quando o n úmero de vértices n diverge. Para este estudo, revisamos algumas ferramentas probabilísticas básicas (convergência de variáveis aleatórias e Métodos do primeiro e segundo momento), que também irão auxiliar ao melhor entendimento de resultados mais complexos. Além disto, aplicamos os conceitos anteriores para um modelo com uma topologia simples, mais especificamente estudamos o comportamento assintótico da probabilidade de não existência de vértices isolados, e discutimos a conectividade ou não do grafo. Por mostramos a convergência em distribuição do número de vértices isolados para uma Distribuição Poisson do modelo estudado.
27
Krüger, Torben [Verfasser], and László [Akademischer Betreuer] Erdős. "Local spectral universality for random matrices with independent entries / Torben Krüger. Betreuer: Laszlo Erdos." München : Universitätsbibliothek der Ludwig-Maximilians-Universität, 2015. http://d-nb.info/1105374211/34.
Full text
28
Newman, Michael William. "Independent Sets and Eigenspaces." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1151.
Full textAbstract:
The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph G. It is known that this is equivalent to determining whether G has a homomorphism into a covering array graph, CAG(n,g). Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of {1,. . . ,n} into g cells each of size at least g, with two vertices being adjacent if their meet has size g2. We determine that CAG(9,3) is a core. We also determine some partial results on the family of graphs CAG(g2,g). The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets ratio-tight. It turns out that CAG(9,3) sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its q-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint k-sets of a fixed v-set, and characterizes the extremal cases. Its q-analogue does the same for k-dimensional subspaces of a fixed v-dimensional space over GF(q). We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the q-analogue. We provide a proof of the characterization of the extremal cases for the q-analogue when v=2k; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph Ω(n) has chromatic number n. The graph Ω(n) has as vertex set the set of all ± 1 vectors of length n, with two vertices adjacent if they are orthogonal. We find that n is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that χ(Ω(n)) > n for all n > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, Ω(n) also sits inside a well-known association scheme, which again plays a central role in our approach.
29
Sartoretto, Eduardo Zorzo. "Conectividade para um modelo de grafo aleatório não homogêneo." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-04102016-145152/.
Full textAbstract:
A caracterização de redes e o estudo de sistemas, ambos utilizando grafos, é algo muito usado por várias áreas científicas. Uma das linhas deste estudo é denominada de grafos aleatórios, que por sua vez auxilia na criação de modelos para análise de redes reais. Consideramos um modelo de grafo aleatório não homogêneo criado por Kang, Pachón e Rodríguez (2016), cuja construção é feita a partir da realização do grafo binomial G(n; p). Para este modelo, estudamos argumentos e métodos usados para encontrar resultados sobre o limiar de conectividade, importante propriedade relacionada a existência assintótica de vértices e componentes isolados. Em seguida, constatamos algumas características positivas e negativas a respeito da utilização do grafo para modelar redes reais complexas, onde usamos de simulações computacionais e medidas topológicas.The characterization of networks and the study of systems, both using graphs, is very used by several scientific areas. One of the lines of this study is called random graphs, which in turn assists in creating models for the analysis of real networks. We consider an inhomogeneous random graph model created by Kang, Pachón e Rodríguez (2016), where its construction is made from the realization of the binomial graph G(n; p). For this model, we studied the arguments and methods used to find results on the connectivity threshold, important property related to asymptotic existence of vertices and isolated components. Then we found some positive and negative characteristics about the use of the graph to model complex real networks, using computer simulations and topological measures.
30
Tiep, Pham H., and Van H. Vu. "Non-abelian Littlewood–Offord inequalities." ACADEMIC PRESS INC ELSEVIER SCIENCE, 2016. http://hdl.handle.net/10150/621530.
Full textAbstract:
In 1943, Littlewood and Offord proved the first anti-concentration result for sums of independent random variables. Their result has since then been strengthened and generalised by generations of researchers, with applications in several areas of mathematics. In this paper, we present the first non-abelian analogue of the Littlewood Offord result, a sharp anti-concentration inequality for products of independent random variables. (C) 2016 Elsevier Inc. All rights reserved.
31
Soosten, Per von [Verfasser], Simone [Akademischer Betreuer] Warzel, László [Gutachter] Erdös, Herbert [Gutachter] Spohn, and Simone [Gutachter] Warzel. "Hierarchical Random Matrices and Operators / Per von Soosten ; Gutachter: László Erdös, Herbert Spohn, Simone Warzel ; Betreuer: Simone Warzel." München : Universitätsbibliothek der TU München, 2018. http://d-nb.info/1161846832/34.
Full text
32
Gomes, Olímpio Ribeiro. "Problemas diretos em Teoria Aditiva via método polinomial : generalização do teorema de Cauchy-Davenport e da conjectura de Erdös-Heilbronn." reponame:Repositório Institucional da UnB, 2008. http://repositorio.unb.br/handle/10482/8782.
Full textAbstract:
Tese (doutorado)-Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2008.Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2011-06-29T19:29:43Z No. of bitstreams: 1 2008_OlimpioRibeiroGomes.pdf: 387344 bytes, checksum: c4d94c8588489c8ec4be6a48ba412e32 (MD5)
Approved for entry into archive by Jaqueline Ferreira de Souza(jaquefs.braz@gmail.com) on 2011-06-29T19:30:35Z (GMT) No. of bitstreams: 1 2008_OlimpioRibeiroGomes.pdf: 387344 bytes, checksum: c4d94c8588489c8ec4be6a48ba412e32 (MD5)
Made available in DSpace on 2011-06-29T19:30:35Z (GMT). No. of bitstreams: 1 2008_OlimpioRibeiroGomes.pdf: 387344 bytes, checksum: c4d94c8588489c8ec4be6a48ba412e32 (MD5)
Sejam subconjuntos finitos e não vazios de um corpo K e seja o polinômio simétrico elementar de grau k em h variáveis. Apresentamos estimativas para o número de elementos dos conjuntos das imagens de todas as h-uplas de pelo polinômio , com e sem a restrição de que os elementos em cada upla sejam dois a dois distintos. Em nosso desenvolvimento somos levados a estudar o conjunto das (0, 1)-matrizes cuja soma dos vetores-linha é igual ao vetor e cuja soma dos vetores-coluna é igual ao vetor . Uma fórmula para o cálculo do número de tais matrizes é apresentada no caso particular em que todas as coordenadas do vetor r são iguais. ______________________________________________________________________________ ABSTRACT
Are finite and non-empty subsets of a field K and is the elementary symmetric polynomial of degree k on m variables. We present estimates for the number of elements of the sets of images of all h-tuples of the polynomial, with and without the restriction that the elements in each tuple are two distinct two. In our development we are led to study the set of (0, 1)-matrices whose sum of row vectors is equal to the vector, the sum of the column vectors is equal to the vector. A formula for calculating the number of such arrays is presented in the particular case where all coordinates of vector r are equal.
33
Depret-Guillaume, James Serge. "Optimal Point Sets With Few Distinct Triangles." Thesis, Virginia Tech, 2019. http://hdl.handle.net/10919/91425.
Full textAbstract:
In this thesis we consider the maximum number of points in $mathbb{R}^d$ which form exactly $t$ distinct triangles, which we denote by $F_d(t)$. We determine the values of $F_d(1)$ for all $dgeq3$, as well as determining $F_3(2)$. It was known from the work of Epstein et al. cite{Epstein} that $F_2(1) = 4$. Here we show somewhat surprisingly that $F_3(1) = 4$ and $F_d(1) = d + 1$, whenever $d geq 3$, and characterize the optimal point configurations. We also show that $F_3(2) = 6$ and give one such optimal point configuration. This is a higher dimensional extension of a variant of the distinct distance problem put forward by ErdH{o}s and Fishburn cite{ErdosFishburn}.Master of Science
In this thesis we consider the following question: Given a number of triangles, t, where each of these triangles are different, we ask what is the maximum number of points that can be placed in d-dimensional space, such that every triplets of these points form the vertices of only the t allowable triangles. We answer this for every dimension, d when the number of triangles is t = 1, as well as show that when t = 2 triangle are in d = 3-dimensional space. This set of questions rises from considering the work of Erd˝os and Fishburn in higher dimensional space [EF].
34
Yilma, Zelealem Belaineh. "Results in Extremal Graph and Hypergraph Theory." Research Showcase @ CMU, 2011. http://repository.cmu.edu/dissertations/49.
Full textAbstract:
In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them.
A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star.
We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed.
We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.
35
Sorakayala, Shashidhar. "Preferences in Musical Rhythms and Implementation of Analytical Results to Generate Rhythms." ScholarWorks@UNO, 2008. http://scholarworks.uno.edu/td/884.
Full textAbstract:
Rhythm is at the heart of all music. It is the variation of the duration of sound over time. A rhythm has two components: one is the striking of an instrument – called the "onset" – and the other is silence. Historically, musical forms and works were preferred and became popular by their rhythmic properties. Therefore, to study rhythm is to study the underpinnings of all of music. In this thesis, we explore basic rhythmic preferences in traditional music and, using this as a point of reference, methods are implemented to generate similar types of rhythms. Finally, a software platform to facilitate such an analysis is developed – it is the first of its kind available to our best knowledge as this research field has only recently emerged.
36
Taha, Samah M. Osman. "Small-world network models and their average path length." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/95834.
Full textAbstract:
Thesis (MSc)--Stellenbosch University, 2014.ENGLISH ABSTRACT: Socially-based networks are of particular interest amongst the variety of communication networks arising in reality. They are distinguished by having small average path length and high clustering coefficient, and so are examples of small-world networks. This thesis studies both real examples and theoretical models of small-world networks, with particular attention to average path length. Existing models of small-world networks, due to Watts and Strogatz (1998) and Newman and Watts (1999a), impose boundary conditions on a one dimensional lattice, and rewire links locally and probabilistically in the former or probabilistically adding extra links in the latter. These models are investigated and compared with real-world networks. We consider a model in which randomness is provided by the Erdos-Rényi random network models superposed on a deterministic one dimensional structured network. We reason about this model using tools and results from random graph theory. Given a disordered network C(n, p) formed by adding links randomly with probability p to a one dimensional network C(n). We improve the analytical result regarding the average path length by showing that the onset of smallworld behaviour occurs if pn is bounded away from zero. Furthermore, we show that when pn tends to zero, C(n, p) is no longer small-world. We display that the average path length in this case approaches infinity with the network order. We deduce that at least εn (where ε is a constant bigger than zero) random links should be added to a one dimensional lattice to ensure average path length of order log n.
AFRIKAANSE OPSOMMING: Sosiaal-baseerde netwerke is van besondere belang onder die verskeidenheid kommunikasie netwerke. Hulle word onderskei deur ’n klein gemiddelde skeidingsafstand en hoë samedrommingskoëffisiënt, en is voorbeelde van kleinwêreld netwerke. Hierdie verhandeling bestudeer beide werklike voorbeelde en teoretiese modelle van klein-wêreld netwerke, met besondere aandag op die gemiddelde padlengte. Bestaande modelle van klein-wêreld netwerke, te danke aan Watts en Strogatz (1998) en Newman en Watts (1999a), voeg randvoorwaardes by tot eendimensionele roosters, en herbedraad nedwerkskakels gebaseer op lokale kennis in die eerste geval en voeg willekeurig ekstra netwerkskakels in die tweede. Hierdie modelle word ondersoek en vergelyk met werklike-wêreld netwerke. Ons oorweeg ’n prosedure waarin willekeurigheid verskaf word deur die Erdös- Renyi toevalsnetwerk modelle wat op ’n een-dimensionele deterministiese gestruktureerde netwerk geimposeer word. Ons redeneer oor hierdie modelle deur gebruik te maak van gereedskap en resultate toevalsgrafieke teorie. Gegewe ’n wanordelike netwerk wat gevorm word deur skakels willekeurig met waarskynlikheid p tot ‘n een-dimensionele netwerk C(n) toe te voeg, verbeter ons die analitiese resultaat ten opsigte van die gemiddelde padlengte deur te wys dat die aanvang van klein-wêreld gedrag voorkom wanneer pn weg van nul begrens is. Verder toon ons dat, wanneer pn neig na nul, C(n, p) nie meer klein-wêreld is nie. Ons toon dat die gemiddelde padlengte in hierdie geval na oneindigheid streef saam met die netwerk groote. Ons lei af dat ten minste εn (waar εn n konstante groter as nul is) ewekansige skakels bygevoeg moet word by ’n een-dimensionele rooster om ‘n gemiddelde padlengte van orde log n te verseker.
37
Ihringer, Ferdinand [Verfasser]. "Finite geometry intersecting algebraic combinatorics : an investigation of intersection problems related to Erdös-Ko-Rado theorems on Galois geometries with help from algebraic combinatorics / Ferdinand Ihringer." Gießen : Universitätsbibliothek, 2015. http://d-nb.info/1076005918/34.
Full text
38
Castro, Paulo Alexandre de. "Rede complexa e criticalidade auto-organizada: modelos e aplicações." Universidade de São Paulo, 2007. http://www.teses.usp.br/teses/disponiveis/76/76131/tde-14012008-165356/.
Full textAbstract:
Modelos e teorias científicas surgem da necessidade do homem entender melhor o funcionamento do mundo em que vive. Constantemente, novos modelos e técnicas são criados com esse objetivo. Uma dessas teorias recentemente desenvolvida é a da Criticalidade Auto-Organizada. No Capítulo 2 desta tese, apresentamos uma breve introdução a Criticalidade Auto-Organizada. Tendo a criticalidade auto-organizada como pano de fundo, no Capítulo 3, estudamos a dinâmica Bak-Sneppen (e diversas variantes) e a comparamos com alguns algoritmos de otimização. Apresentamos no Capítulo 4, uma revisão histórica e conceitual das redes complexas. Revisamos alguns importantes modelos tais como: Erdös-Rényi, Watts-Strogatz, de configuração e Barabási-Albert. No Capítulo 5, estudamos o modelo Barabási-Albert não-linear. Para este modelo, obtivemos uma expressão analítica para a distribuição de conectividades P(k), válida para amplo espectro do espaço de parâmetros. Propusemos também uma forma analítica para o coeficiente de agrupamento, que foi corroborada por nossas simulações numéricas. Verificamos que a rede Barabási-Albert não-linear pode ser assortativa ou desassortativa e que, somente no caso da rede Barabási-Albert linear, ela é não assortativa. No Capítulo 6, utilizando dados coletados do CD-ROM da revista Placar, construímos uma rede bastante peculiar -- a rede do futebol brasileiro. Primeiramente analisamos a rede bipartida formada por jogadores e clubes. Verificamos que a probabilidade de que um jogador tenha participado de M partidas decai exponencialmente com M, ao passo que a probabilidade de que um jogador tenha marcado G gols segue uma lei de potência. A partir da rede bipartida, construímos a rede unipartida de jogadores, que batizamos de rede de jogadores do futebol brasileiro. Nessa rede, determinamos várias grandezas: o comprimento médio do menor caminho e os coeficientes de agrupamento e de assortatividade. A rede de jogadores de futebol brasileiro nos permitiu analisar a evolução temporal dessas grandezas, uma oportunidade rara em se tratando de redes reais.Models and scientific theories arise from the necessity of the human being to better understand how the world works. Driven by this purpose new models and techniques have been created. For instance, one of these theories recently developed is the Self-Organized Criticality, which is shortly introduced in the Chapter 2 of this thesis. In the framework of the Self-Organized Criticality theory, we investigate the standard Bak-Sneppen dynamics as well some variants of it and compare them with optimization algorithms (Chapter 3). We present a historical and conceptual review of complex networks in the Chapter 4. Some important models like: Erdös-Rényi, Watts-Strogatz, configuration model and Barabási-Albert are revised. In the Chapter 5, we analyze the nonlinear Barabási-Albert model. For this model, we got an analytical expression for the connectivity distribution P(k), which is valid for a wide range of the space parameters. We also proposed an exact analytical expression for the clustering coefficient which corroborates very well with our numerical simulations. The nonlinear Barabási-Albert network can be assortative or disassortative and only in the particular case of the linear Barabási-Albert model, the network is no assortative. In the Chapter 6, we used collected data from a CD-ROM released by the magazine Placar and constructed a very peculiar network -- the Brazilian soccer network. First, we analyzed the bipartite network formed by players and clubs. We find out that the probability of a footballer has played M matches decays exponentially with M, whereas the probability of a footballer to score G gols follows a power-law. From the bipartite network, we built the unipartite Brazilian soccer players network. For this network, we determined several important quantities: the average shortest path length, the clustering coefficient and the assortative coefficient. We were also able to analise the time evolution of these quantities -- which represents a very rare opportunity in the study of real networks.
39
Zhao, Meng John. "Analysis and Evaluation of Social Network Anomaly Detection." Diss., Virginia Tech, 2017. http://hdl.handle.net/10919/79849.
Full textAbstract:
As social networks become more prevalent, there is significant interest in studying these network data, the focus often being on detecting anomalous events. This area of research is referred to as social network surveillance or social network change detection. While there are a variety of proposed methods suitable for different monitoring situations, two important issues have yet to be completely addressed in network surveillance literature. First, performance assessments using simulated data to evaluate the statistical performance of a particular method. Second, the study of aggregated data in social network surveillance. The research presented tackle these issues in two parts, evaluation of a popular anomaly detection method and investigation of the effects of different aggregation levels on network anomaly detection.Ph. D.
40
Aloui, Karam. "Propriétés arithmétiques et combinatoires de la fonction somme des chiffres." Thesis, Aix-Marseille, 2014. http://www.theses.fr/2014AIXM4083/document.
Full textAbstract:
L'objet de cette thèse est l'étude de certaines propriétés arithmétiques et combinatoires de la fonction somme des chiffres. Nous commençons par étudier les sommes d'exponentielles de la forme $dissum_{nleq x}expleft(2ipileft(frac{l}{m}S_q(n)+frac{k}{m'}S_{q}(n+1)+theta nright)right)$ en vue de montrer un résultat d'équirépartition modulo $1$ et un théorème probabiliste d'ErdH{o}s-Kac. Ensuite, on va généraliser un problème dû à Gelfond concernant l'étude de la répartition dans les progressions arithmétiques de la fonction somme des chiffres au cas des nombres ellipséphiques. En particulier, on donne un théorème analogue à celui d'Erdös, Mauduit et S'arközy sur l'uniforme répartition des entiers ellipséphiques dans les progressions arithmétiques sous une contrainte sur la somme des chiffres. Enfin, une étude de l'ordre moyen de certaines fonctions arithmétiques soumises à des contraintes digitales est faite en conséquence des travaux de Mkaouar et WannèsThe aim of this thesis is the study of some arithmetic and combinatoric properties of the sum of digits function. We start by the study of exponential sums of the form $dissum_{nleq x}expleft(2ipileft(frac{l}{m}S_q(n)+frac{k}{m'}S_q(n+1)+theta nright)right)$ in order to establish a result of equidistribution modulo $1$ in addition to a probabilistic theorem of the kind ErdH{o}s-Kac. Then, we generalize a problem due to Gelfond concerning the distribution in residue classes of the sum of digits function in the case of integers with missing digits. Besides, we give a similar result to that of ErdH{o}s, Mauduit and S'ark"{o}zy on the uniform distribution of integers with missing digits in arithmetic progressions under a constraint on the sum of digits. Finally, a study of the order of magnitude of some arithmetical functions under digital constraints is done as a consequence of the works of Mkaouar and Wannès
41
Butz, Maximilian Josef [Verfasser], Herbert [Akademischer Betreuer] Spohn, László [Akademischer Betreuer] Erdös, and Simone [Akademischer Betreuer] Warzel. "Kinetic limit for wave propagation in a continuous, weakly random medium : Self-averaging and convergence to a linear Boltzmann equation / Maximilian Josef Butz. Gutachter: László Erdös ; Herbert Spohn ; Simone Warzel. Betreuer: Herbert Spohn." München : Universitätsbibliothek der TU München, 2015. http://d-nb.info/1076625576/34.
Full text
42
Davis, Tiana. "Quantifying Chlorophyll a Content Through Remote Sensing: A Pilot Study of Utah Lake." Diss., CLICK HERE for online access, 2006. http://contentdm.lib.byu.edu/ETD/image/etd1261.pdf.
Full text
43
Raymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT289.
Full textAbstract:
Le thème central à cette thèse est l'étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications.La première direction que nous suivons a trait aux beaux ordres. À l'aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille.La troisième direction est l'étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultatsThe central theme of this thesis is the study of the properties of the classes of graphs defined by forbidden substructures and their applications.The first direction that we follow concerns well-quasi-orders. Using decomposition theorems on graph classes forbidding one substructure, we identify those that are well-quasi-ordered. The orders and substructures that we consider are those related to the notions of contraction and induced minor.Then, still considering classes of graphs defined by forbidden substructures, we obtain bounds on invariants such as degree, treewidth, tree-cut width, and a new invariant generalizing the girth.The third direction is the study of the links between the combinatorial invariants related to problems of packing and covering of graphs. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results
44
Brunk, Fiona. "Intersection problems in combinatorics." Thesis, St Andrews, 2009. http://hdl.handle.net/10023/765.
Full text
45
Lagoutte, Aurélie. "Interactions entre les Cliques et les Stables dans un Graphe." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1012/document.
Full textAbstract:
Cette thèse s'intéresse à différents types d'interactions entre les cliques et les stables, deux objets très importants en théorie des graphes, ainsi qu'aux relations entre ces différentes interactions. En premier lieu, nous nous intéressons au problème classique de coloration de graphes, qui peut s'exprimer comme une partition des sommets du graphe en stables. Nous présentons un résultat de coloration pour les graphes sans triangles ni cycles pairs de longueur au moins 6. Dans un deuxième temps, nous prouvons la propriété d'Erdös-Hajnal, qui affirme que la taille maximale d'une clique ou d'un stable devient polynomiale (contre logarithmique dans les graphes aléatoires) dans le cas des graphes sans chemin induit à k sommets ni son complémentaire, quel que soit k.Enfin, un problème moins connu est la Clique-Stable séparation, où l'on cherche un ensemble de coupes permettant de séparer toute clique de tout stable. Cette notion a été introduite par Yannakakis lors de l’étude des formulations étendues du polytope des stables dans un graphe parfait. Il prouve qu’il existe toujours un séparateur Clique-Stable de taille quasi-polynomiale, et se demande si l'on peut se limiter à une taille polynomiale. Göös a récemment fourni une réponse négative, mais la question se pose encore pour des classes de graphes restreintes, en particulier pour les graphes parfaits. Nous prouvons une borne polynomiale pour la Clique-Stable séparation dans les graphes aléatoires et dans plusieurs classes héréditaires, en utilisant notamment des outils communs à l'étude de la conjecture d'Erdös-Hajnal. Nous décrivons également une équivalence entre la Clique-Stable séparation et deux autres problèmes : la conjecture d'Alon-Saks-Seymour généralisée et le Problème Têtu, un problème de Satisfaction de ContraintesThis thesis is concerned with different types of interactions between cliques and stable sets, two very important objects in graph theory, as well as with the connections between these interactions. At first, we study the classical problem of graph coloring, which can be stated in terms of partioning the vertices of the graph into stable sets. We present a coloring result for graphs with no triangle and no induced cycle of even length at least six. Secondly, we study the Erdös-Hajnal property, which asserts that the maximum size of a clique or a stable set is polynomial (instead of logarithmic in random graphs). We prove that the property holds for graphs with no induced path on k vertices and its complement.Then, we study the Clique-Stable Set Separation, which is a less known problem. The question is about the order of magnitude of the number of cuts needed to separate all the cliques from all the stable sets. This notion was introduced by Yannakakis when he studied extended formulations of the stable set polytope in perfect graphs. He proved that a quasi-polynomial number of cuts is always enough, and he asked if a polynomial number of cuts could suffice. Göös has just given a negative answer, but the question is open for restricted classes of graphs, in particular for perfect graphs. We prove that a polynomial number of cuts is enough for random graphs, and in several hereditary classes. To this end, some tools developed in the study of the Erdös-Hajnal property appear to be very helpful. We also establish the equivalence between the Clique-Stable set Separation problem and two other statements: the generalized Alon-Saks-Seymour conjecture and the Stubborn Problem, a Constraint Satisfaction Problem
46
Liao, Yi-Hsun, and 廖奕勛. "Finding independent sets of Erdős–Rényi random graphs." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/qt5ugy.
Full textAbstract:
碩士元智大學
資訊工程學系
107
The Erdős–Rényi random graph G(n,p) is an n-vertex graph which includes each of the (n¦2) edges with probability p independently of all other edges. The Bron–Kerbosch algorithm finds all maximal independent sets of any undirected graph G=(V,E) in Ο(3^(|V|∕3) )= Ο(〖1.4422〗^(|V|) ) time. Our experiments show that as p increases, the expected number of maximal independent sets of G(n,p) increases sharply and then decreases slowly. Furthermore, as p increases, the expected running time of the Bron–Kerbosch algorithm on G(n,p) increases sharply, decreases sharply and then increases slowly.
47
Wun, Fu-Cyuan, and 溫福銓. "Discussing the Happy Ending problem from the Paul Erdős-Szekeres Theory." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/55678263536694566103.
Full textAbstract:
碩士國立屏東教育大學
應用數學系
99
In 1935, Esther Klein [1] asked, “Is it true that for every n, there is a least value g(n) such that any set of g(n) points in the plane in general position always contains the vertices of a convex n-gon?” This is the “Happy Ending problem” because it led to the marriage of George Szekeres and Esther Klein. In this paper, we show the existence of g(n) and estimate its upper bound and lower bound by using the Erdős-Szekeres Theorem. We also constructing explicit examples for the minimal possible g(n) for a set of g(n) points in the plane in general position must contain a convex n-gon.
48
Eliáš, Marek. "Erdos-Szekeres type theorems." Master's thesis, 2012. http://www.nusl.cz/ntk/nusl-304489.
Full textAbstract:
Let P = (p1, p2, . . . , pN ) be a sequence of points in the plane, where pi = (xi, yi) and x1 < x2 < · · · < xN . A famous 1935 Erdős-Szekeres theorem asserts that every such P contains a monotone subsequence S of √ N points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Ω(log N) points. First we define a (k + 1)-tuple K ⊆ P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S ⊆ P is kth-order monotone if its (k + 1)- tuples are all positive or all negative. In this thesis we investigate quantitative bound for the corresponding Ramsey-type result. We obtain an Ω(log(k−1) N) lower bound ((k − 1)-times iterated logarithm). We also improve bounds for related problems: Order types and One-sided sets of hyperplanes. 1
49
Balko, Martin. "Ramseyovské výsledky pro uspořádané hypergrafy." Doctoral thesis, 2016. http://www.nusl.cz/ntk/nusl-267853.
Full textAbstract:
Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by Károlyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...
50
Damelin, Steven Benjamin. "Weighted approximation for Erdðs weights." Thesis, 1995. http://hdl.handle.net/10539/22133.
Full textAbstract:
We investigate Mean Convergence of Lagrange Interpolation and Rates of Approximation
for Erd5's Weights on the Real line.
An Erdg's Weight is of the form, W : • expI-Q]' where typically Q is even,
continuous and is of faster than polynomial growth at infinity.
Concerning Lagrange Interpolation, we obtain necessaryand sufficient conditions
for convergence in Lp (1::; p < 00) and in particular, sharp results for p > 4 and
1 MN (2017)