999 research outputs found
An Erdos-Hajnal conjecture
No full textUm resultado de Erdos demonstra a existência de grafos com número cromático e cintura arbitrariamente grandes. Temos então que um clique suficientemente grande contém um grafo com número cromático e cintura grandes como subgrafo, porém muitos grafos de interesse não necessariamente contém cliques grandes, então é interessante encontrar outra condição que garanta a existência de subgrafos com número cromático e cintura grandes. Uma conjectura de Erdos e Hajnal diz que todo grafo com número cromático suficientemente grande contém um subgrafo com número cromático e cintura grandes. O objetivo deste trabalho é estudar tal conjectura. O texto começa com uma breve apresentação de construções livres de triângulos. Em particular, é demonstrada uma construção de Codenotti, Pudlák e Resta, por meio de planos projetivos. O tópico principal do texto começa com uma demonstração de Rödl de que todo grafo com número cromático suficientemente grande contém um subgrafo livre de triângulos e com número cromático grande. Em sequência, apresentaremos uma demonstração de que grafos com número cromático suficientemente grande contém algum circuito ímpar grande. Apresentaremos também um resultado de Mohar e Wu, que demonstra que a família dos grafos de Kneser respeita a conjectura de Erdos e Hajnal. Outro resultado apresentado é de Gábor Tardos, demonstrando que a família dos shift graphs respeita a conjectura de Erdos e Hajnal. E por fim apresentaremos alguns breves resultados sobre os type graphs, mostrando casos que respeitam a conjectura de Erdos e Hajnal.A result by Erdos shows that there exist graphs with arbitrarily large chromatic number and girth. Thus a sufficiently large clique contains a subgraph with large chromatic number and girth, but many graphs do not have a large clique, hence it is interesting to find a different condition that guarantees the existence of a subgraph with large chromatic number and girth. A conjecture by Erdos and Hajnal states that every graph with sufficiently large chromatic number contains a subgraph with large chromatic number and girth. The objective of this text is to study this conjecture. The text begins with a brief discussion of triangle-free constructions. In particular, we show a construction by Codenotti, Pudlák and Resta, based on projective planes. The main topic begins with a proof by Rödl, that every graph with sufficiently large chromatic number contains a triangle-free subgraph with large chromatic number. We follow with a proof that every graph with sufficiently large chromatic number contains a large odd cycle. We then show a result by Mohar and Wu, which shows that the Kneser graphs respect the Erdos-Hajnal conjecture. Another result by Gábor Tardos proves that shift graphs also respect the Erdos-Hajnal conjecture. Finally, we show some brief results about type graphs, showing some cases that follow the Erdos-Hajnal conjecture
Erdos Conjecture I.
No full textIn this short paper I show how it is related to other famous unsolved problems in
prime number theory. In order to do this, I formulate the main hypothetical result of this paper - a useful upper bound conjecture (Conjecture 3.), describing one aspect of the distribution of primes in various special forms, paying a brief attention to Fermat, Mersenne, Fibonacci, Lucas and Smarandache sequences, and I debate some side effects of the most surprising results it implies. At
the end I also give connections of the questions discussed to other important areas of prime number theory, such as topics from the theory of distribution of primes in denser sequences, and along the way I mention some further conjectures of Erdos that have relevant applications there
ON THE CONVERGENCE OF THE EULER HARMONIC SERIES
No full textThe aim oj this article is to study the convergence oj the Euler harmonic series. Firstly, the results concerning the convergence oj the Smaralldache and Erdos harmonic junctions are reviewed Secondly, the Euler harmonic series is proved to be convergent for a> 1, and divergent otherwise. Finally, the slims of the Euler harmonic series are given
ADJUSTING A CONJECTURE OF ERDOS
No full textFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)We investigate a conjecture of Paul Erdos, the last unsolved problem among those proposed in his landmark paper [2]. The conjecture states that there exists an absolute constant C > 0 such that, if, v are unit vectors in a Hilbert space, then at least C2(n)/n of all epsilon is an element of {-1, 1}(n) are such that vertical bar Sigma(n)(i=1) epsilon(i)v(i) vertical bar 2, the counterexample is quite strong, and implies that a substantial weakening of the conjecture is necessary. However, for d = 2, only a minor modification is necessary, and it seems to us that it remains a hard problem, worthy of Erdos. We prove some weaker related results that shed some light on the hardness of the problem.61154159Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)FAPESP [2004/14107-2]CNPq [300702/2005-1
Packing Cycles Faster Than Erdos-Posa
No full textThe Cycle Packing problem asks whether a given undirected graph G=(V,E) contains k vertex-disjoint cycles. Since the publication of the classic Erdos-Posa theorem in 1965, this problem received significant scientific attention in the fields of Graph Theory and Algorithm Design. In particular, this problem is one of the first problems studied in the framework of Parameterized Complexity. The non-uniform fixed-parameter tractability of Cycle Packing follows from the Robertson–Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2^{O(k^2)}|V| using exponential space. In case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2^{O(k\log^2 k)}|V|-time (deterministic) algorithm using exponential space, which is a consequence of the Erdos-Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on Parameterized Complexity. Yet, no algorithm that runs in time 2^{o(k\log^2k)}|V|^{O(1)}, beating the bound 2^{O(k\log^2k)}\cdot |V|^{O(1)}, has been found. In light of this, it seems natural to ask whether the 2^{O(k\log^2k)}|V|^{O(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a 2^{O(k\log^2k/log log k})} |V|-time (deterministic) algorithm for Cycle Packing. In case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the known bound, our algorithm runs in time linear in |V|, and its space complexity is polynomial in the input size
Apresentações do Teorema de Erdos-Mordell
No full textO 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
Fluid limit for the Erdos-Rényi random graph
No full textNeste 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)
A NEW PROOF OF THE ERDOS-KAC CENTRAL LIMIT THEOREM
No full textIn this paper we use the Riemann zeta distribution to give a new proof of the Erdos-Kac Central Limit Theorem. That is, if zeta(s) = Sigma(n >= 1) (1)(s)(n) , s > 1, then we consider the random variable X-s with P(X-s = n) = (1) (zeta) (s)n(s), n >= 1. In an earlier paper, the first author and Adrien Peltzer derived the analog of the Erdos-Kac Central Limit Theorem (CLT) for the number of distinct prime factors, omega(X-s), of X-s, as s SE arrow 1. In this paper we show, by means of a Tauberian Theorem, how to obtain the Central Limit Theorem of Erdos-Kac for the uniform distribution from the result for the random variable X-s. We also apply the technique to the number of distinct prime divisors of X-s that lie in an arithmetic sequence and a local CLT of the type proved by Dixit and Murty [Hardy-Ramanujan J. 43 (2020), 17-23] as well a version of the CLT for irreducible divisors of a monic polynomial over a finite field.PRS
Unveiling employee perceptions: Navigating Erdos Group's path to sustainable development and ESG strategies
No full textThe concepts of sustainable development and ESG are currently hot research topics in the
field of corporate development. As a multi-sector enterprise, Erdos possesses extensive
practical experience in these areas. To investigate employees' attitudes towards the current
implementation of policies, a combination of questionnaire surveys and interviews was
employed. This study unveils the internal variations in the perception of relevant concepts
within Erdos, along with the clear stance of top management. By analyzing and integrating
the results from both surveys, this research provides the group with a clearer direction for
future progress in the realms of sustainable development and ESG.Os conceitos de desenvolvimento sustentável e ESG são tópicos atuais pesquisa no campo do
desenvolvimento empresarial. O facto de a Erdos ser uma empresa com vários negócios
permite-lhe ter uma grande experiência nos assuntos relacionados com o desenvolvimento
sustentável. Com o intuito de investigar as atitudes dos funcionários em relação à
implementação das políticas relacionadas com o desenvolvimento sustentável utilizamos uma
abordagem mista de pesquisa (questionário à generalidade dos funcionários e entrevistas aos
gestores de topo). Este estudo revela variações internas nas percepções dos conceitos
relevantes dentro da empresa em estudo, a Erdos. A análise e integração dos resultados dos
questionários e entrevistas da pesquisa efetuada fornece ao grupo uma direção mais clara para
futuros progressos na formulação e implementação de estratégias nos domínios do
desenvolvimento sustentável e ESG
On torsion in eulerian magnitude homology of Erdos-Renyi random graphs
No full textIn this paper we investigate the regimes where an Erdos-Renyi random graph has torsion free eulerian magnitude homology groups. To this end, we start be introducing the eulerian Asao-Izumihara complex - a quotient CW-complex whose homology groups are isomorphic to direct summands of the graph eulerian magnitude homology group. We then proceed by producing a vanishing threshold for a shelling of eulerian Asao-Izumihara complex. This will lead to a result establishing the regimes where eulerian magnitude homology of Erdos-Renyi random graphs is torsion free.14 page
- …
