Nós consideramos o seguinte problema. Fixado um grafo H e um número real \\alpha \\in (0,1], determine o menor \\beta = \\beta(\\alpha, H) que satisfaz a seguinte propriedade: se G é um grafo de ordem n no qual cada subconjunto de [\\alpha n] vértices induz mais que \\beta n^2 arestas então G contém H como subgrafo. Este problema foi iniciado e motivado por Erdös ao conjecturar que todo grafo livre de triângulo de ordem n contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Nosso resultado principal mostra que i) todo grafo de ordem n livre de triângulos e pentágonos contém um subconjunto de [n/2] vértices que induz no máximo n^2 /64 arestas, e ii) se G é um grafo regular de ordem n livre de triângulo, com grau excedendo n/3, então G contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Se além disso G não é 3-cromático então G contém um subconjunto de [n/2] vértices que induz menos de n^2 /54 arestas. Como subproduto e confirmando uma conjectura de Erdös assintoticamente, temos que todo grafo regular de ordem n livre de triângulo com grau excedendo n/3 pode ser tornado bipartido pela omissão de no máximo (1/25 + o(1))n^2 arestas. Nós também fornecemos um contraexemplo a uma conjectura de Erdös, Faudree, Rousseau e Schelp. / We consider the following problem. Fixed a graph H and a real number \\alpha \\in (0,1], determine the smallest \\beta = \\beta(\\alpha, H) satisfying the following property: if G is a graph of order n such that every subset of [\\alpha n] vertices spans more that \\beta n^2 edges then G contains H as a subgraph. This problem was initiated and motivated by Erdös who conjectured that every triangle-free graph of order n contains a subset of [n/2] vertices that spans at most n^2 /50 edges. Our main result shows that i) every triangle- and pentagon-free graph of order n contains a subset of [n/2] vertices inducing at most n^2 /64 edges and, ii) if G is a triangle-free regular graph of order n with degree exceeding n/3 then G contains a subset of [n/2] vertices inducing at most n^2 /50 edges. Furthermore, if G is not 3-chromatic then G contains a subset of [n/2] vertices inducing less than n^2 /54 edges. As a by-product and confirming a conjecture of Erdös asymptotically, we obtain that every n-vertex triangle-free regular graph with degree exceeding n/3 can be made bipartite by removing at most (1/25 + o(1))n^2 edges. We also provide a counterexample to a conjecture of Erdös, Faudree, Rousseau and Schelp.

Nós consideramos o seguinte problema. Fixado um grafo H e um número real \\alpha \\in (0,1], determine o menor \\beta = \\beta(\\alpha, H) que satisfaz a seguinte propriedade: se G é um grafo de ordem n no qual cada subconjunto de [\\alpha n] vértices induz mais que \\beta n^2 arestas então G contém H como subgrafo. Este problema foi iniciado e motivado por Erdös ao conjecturar que todo grafo livre de triângulo de ordem n contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Nosso resultado principal mostra que i) todo grafo de ordem n livre de triângulos e pentágonos contém um subconjunto de [n/2] vértices que induz no máximo n^2 /64 arestas, e ii) se G é um grafo regular de ordem n livre de triângulo, com grau excedendo n/3, então G contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Se além disso G não é 3-cromático então G contém um subconjunto de [n/2] vértices que induz menos de n^2 /54 arestas. Como subproduto e confirmando uma conjectura de Erdös assintoticamente, temos que todo grafo regular de ordem n livre de triângulo com grau excedendo n/3 pode ser tornado bipartido pela omissão de no máximo (1/25 + o(1))n^2 arestas. Nós também fornecemos um contraexemplo a uma conjectura de Erdös, Faudree, Rousseau e Schelp. / We consider the following problem. Fixed a graph H and a real number \\alpha \\in (0,1], determine the smallest \\beta = \\beta(\\alpha, H) satisfying the following property: if G is a graph of order n such that every subset of [\\alpha n] vertices spans more that \\beta n^2 edges then G contains H as a subgraph. This problem was initiated and motivated by Erdös who conjectured that every triangle-free graph of order n contains a subset of [n/2] vertices that spans at most n^2 /50 edges. Our main result shows that i) every triangle- and pentagon-free graph of order n contains a subset of [n/2] vertices inducing at most n^2 /64 edges and, ii) if G is a triangle-free regular graph of order n with degree exceeding n/3 then G contains a subset of [n/2] vertices inducing at most n^2 /50 edges. Furthermore, if G is not 3-chromatic then G contains a subset of [n/2] vertices inducing less than n^2 /54 edges. As a by-product and confirming a conjecture of Erdös asymptotically, we obtain that every n-vertex triangle-free regular graph with degree exceeding n/3 can be made bipartite by removing at most (1/25 + o(1))n^2 edges. We also provide a counterexample to a conjecture of Erdös, Faudree, Rousseau and Schelp.

The Turán problem is a fundamental problem in extremal graph theory. It asks what the maximum number of edges a given graph G can have, not containing some forbidden graph H, and is solved using the Turán number ex(n,H), density π(H) and graph Tr(n). Turán's theorem tells us that the Turán graph Tr(n) is the largest Kr+1-free simple graph on n vertices. This paper is an overview of Turán problems for cliques Kn, hypercubes Qn and Hamming graphs H(s,d). We end it by proving a new result we call "the layer theorem", solving the Hamming-Turán problem using a method of creating layers of vertices in a graph. This theorem gives a lower bound for the Hamming-relative Turán density as follows: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cpi_%7Bs,d%7D(%5Cmathcal%7BH%7D_%7Bs,d%7D,F)%20%5Cgeq%201%20-%20%5Cdfrac%7Bf+g%7D%7B%7C%7CH(s,d)%7C%7C%7D" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?f%20=%20%5Cbinom%7Bs%7D%7B2%7D%5Cleft(1-%5Cdfrac%7Br-2%7D%7Br-1%7D%5Cright)ds%5E%7Bd-1%7D%20%5Ctext%7B%20and%20%7D%20g%20=%20%5Csum_%7Bi=1%7D%5E%7Bn/(t-1)%7D%20(d-i(t-1))(s-1)%5E%7Bi(t-1)+1%7D%5Cbinom%7Bd%7D%7Bi(t-1)%7D" /> for the forbidden graph F stretching over t layers and r = χ(F). / Turán-problemet är det fundamentala problemet inom extremal grafteori. Det ställer frågan vad det maximala antalet kanter en given graf G kan ha utan att innehålla någon förbjuden graf H, och löses med hjälp av Turán-talet ex(n,H), -densiteten π(H) and -grafen Tr(n). Turáns sats säger oss att Turán-grafen Tr(n) är den största Kr+1-fria enkla grafen på n hörn. Denna uppsats är en överblick av Turán-problem i klickar Kn, hyperkuber Qn och Hamming-grafer H(s,d). Vi avslutar den med att bevisa ett nytt resultat som vi kallar "lagersatsen", vilket löser Hamming-Turán-problemet med hjälp av en metod som skapar lager av hörnen i en graf. Lagersatsen ger en undre gräns för den Hamming-relativa Turán-densiteten enligt följande: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cpi_%7Bs,d%7D(%5Cmathcal%7BH%7D_%7Bs,d%7D,F)%20%5Cgeq%201%20-%20%5Cdfrac%7Bf+g%7D%7B%7C%7CH(s,d)%7C%7C%7D" /> där <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?f%20=%20%5Cbinom%7Bs%7D%7B2%7D%5Cleft(1-%5Cdfrac%7Br-2%7D%7Br-1%7D%5Cright)ds%5E%7Bd-1%7D%20%5Ctext%7B%20and%20%7D%20g%20=%20%5Csum_%7Bi=1%7D%5E%7Bn/(t-1)%7D%20(d-i(t-1))(s-1)%5E%7Bi(t-1)+1%7D%5Cbinom%7Bd%7D%7Bi(t-1)%7D" /> för den förbjudna grafen F som sträcker sig över t lager samt r = χ(F).

La géométrie combinatoire est une large et belle branche des mathématiques. Cette thèse doctorale se compose de l'étude de cinq sujets différents dans ce domaine. Même si les problèmes et les techniques utilisés pour y faire face sont divers, ils partagent le mêeme objectif: Étudier l'interaction entre les structures combinatoires et géométriques. Dans le chapitre 1, nous étudions le problème suivant : pour un entier positif k, combien de points en position générale devons-nous prendre dans le plan de sorte que nous pouvons toujours trouver k d'entre eux définissant des triangles avec un rayon du cercle circonscrit distinct ? Cette question a été posée par Paul Erdös en 1975 qui a lui même proposé une solution en 1978. Toutefois, la preuve a omis par inadvertance un cas non trivial. Nous avons repris ce cas et donné une solution à la question en utilisant des outils de base de la géométrie algébrique et nous fournissons une borne polynomiale pour le nombre de points nécessaires.Dans le chapitre 2, nous sommes intéressés par de généralisations géométriques du critère de Hall pour les couplages dans les graphes bipartits (1935). Nous obtenons des théorèmes géométriques type Hall pour des ensembles convexes disjoints et pour points en position générale dans l'espace euclidien. Les outils de ce chapitre sont topologiques, et l'approche est motivés par une méthode remarquable introduite par Aharoni et Haxell en $2000$ ainsi que par ses généralisations.D'autre part, dans le chapitre 3, nous commençons par un théorème de Helly fractionné de 1979 due à A. Liu et M. Katchalski pour motiver un résultat combinatoire. Nous étudions des conditions combinatoires que des familles de graphes doivent avoir pour permettre d'obtenir des versions plus fine du théorème de Turán. Nous trouvons des liens intéressants entre les nombres de Turán, les nombres chromatiques et les nombres de clique dans la famille. Les outils de ce chapitre sont purement combinatoires.Dans le chapitre 4, nous nous concentrons sur l'obtention des résultats pour la bien connue classe des matroïde chemin du réseau introduite par Bonin, de Mier et Noy en 2003. La contribution principale est de prouver pour cette classe la validité d'une conjecture de Merino et Welsh (1999) sur une inégalité de certaines valeurs du polynôme de Tutte. Pour ce faire, nous introduisons et étudions des serpents, une classe spéciale de matroïdes chemin du réseau ``mince''.Enfin, dans le chapitre 5, nous étudions une variante d'un problème des transversales posé par J.L. Arocha, J. Bracho, L. Montejano et J.L. Ramírez-Alfonsín en 2010. Dans leur travaux originaux, ils ont rémarqué que si nous avons peu de points dans l'espace euclidien alors il est possible de trouver une transversale d'une dimension donnée qui travers les enveloppes convexes de tous les k-ensembles de points. De m&eme, ils montrent qu'il est impossible de trouver une telle transversale lorsque nous avons beaucoup de points. Les auteurs donnent des bornes spécifiques et ils laissent aussi quelques problèmes ouverts. Si la définition de transversale est légèrement plus restrictive, alors le problème peut être étudié en utilisant la théorie des matroïdes orientés. Dans la présente thèse, nous fournissons les détails de cette relation et nous donnons des bornes pour la famille de polytopes cycliques. / Combinatorial geometry is a broad and beautiful branch of mathematics. This PhD Thesis consists of the study of five different topics in this area. Even though the problems and the tools used to tackle them are diverse, they share a unifying goal: To explore the interaction between combinatorial and geometric structures.In Chapter 1 we study a problem by Paul Erdös: for a positive integer k, how many points in general position do we need in the plane so that we can always find a k-subset of them defining triangles with distinct circumradii? This question was posed in 1975 and Erdös himself proposed a solution in 1978. However, the proof inadvertently left out a non-trivial case. We deal with the case using basic tools from algebraic geometry and we provide a polynomial bound for the needed number of points.In Chapter 2 we are interested in providing geometric extensions of Hall's criterion for matchings in bipartite graphs (1935). We obtain geometric Hall-type theorems for pairwise disjoint convex sets and for points in general position in euclidean space. The tools of this chapter are topological, and are motivated by a remarkable method introduced by Aharoni and Haxell in 2000 and its generalizations.On the other hand, in Chapter 3 we begin with a fractional Helly theorem from 1979 by A. Liu and M. Katchalski to motivate a combinatorial result. We study combinatorial conditions on families of graphs that allow us to have sharpened variants of Turán's theorem. We find interesting relations between the Turán numbers, the chromatic numbers and the clique numbers of graphs in the family. The tools in this chapter are only combinatorial.In Chapter 4 we focus on obtaining some results for the well studied class of lattice path matroids introduced by Bonin, de Mier and Noy in 2003. The main contribution is proving for this class the validity of a 1999 conjecture of Merino and Welsh concerning an inequality involving certain values of the Tutte polynomial. In order to do this, we introduce and study snakes, a special class of ``thin'' lattice path matroids.Finally, in Chapter 5 we explore a variant of a transversal problem posed by J.L. Arocha, J. Bracho, L. Montejano and J.L. Ramírez-Alfonsín in 2010. In their original work, they realized that if we have few points in euclidean space then it is possible to find a transversal of a given dimension that goes through all the convex hulls of k-subsets of points. Similarly, they show that it is impossible to find such a transversal when we have many points. The authors give some specific bounds and they also leave some open problems. If the definition of transversal is slightly more restrictive, then the problem can be tackled using oriented matroid theory. We provide the details of the relation and we give bounds for the family of cyclic polytopes.