Let F0 be a fixed k-uniform hypergraph, and let H be a given k-uniform hypergraph on n vertices. An F0-packing of H is a family F of edge-disjoint copies of F0 which are subhypergraphs in H. Let nF0(H) denote the maximum size |F| of an F0-packing F of H. It is well-known that computing nF0(H) is NP-hard for nearly any choice of F0. In this thesis, we consider the special case when F0 is a linear hypergraph, that is, when no two edges of F0 overlap in more than one vertex. We establish for z > 0 and n &ge n0(z) sufficiently large, an algorithm which, in time polynomial in n, constructs an F0-packing F of H of size |F| ≥ nF0(H) - znk. A central direction in our proof uses so-called fractional F0-packings of H which are known to approximate nF0(H). The driving force of our argument, however, is the use and development of several tools within the theory of hypergraph regularity.

No description available.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Cette thèse traite de problèmes liés à la théorie des limitesd'objets combinatoires, une récente théorie qui a permis de tisserdes liens entre différents domaines tels que la combinatoire,l'analyse, la géométrie ou la théorie de la probabilité.Cette thèse applique des méthode venant de cette théorie à des problèmesde combinatoire extrémale.Dans un premier chapitre, je développe une théorie des limites d'objetsappelés emph{types d'ordre}, un objets qui encode des configurationsd'ensembles de points du plan. Le type d'ordre d'un ensemble de pointssuffit à caractériser de nombreuses propriétés essentielles de cet ensemblede point comme, par exemple, son enveloppe convexe.Je montre qu'une limite de type d'ordre peut être représentée par un objetanalogue à un graphon à valeurs O ou 1.Je fais ensuite le lien entre limites de type d'ordre et la distributionnaturelle de limite de type d'ordre obtenue par l’échantillonnage de pointsdu plan suivant une certaine probabilité.De cette manière, toute probabilité sur le plan engendre une limite de typed'ordre. Je montre d'une part que cette correspondance n'est pas surjective-c'est à dire qu'il existe des limites de type d'ordre ne venant pas de probabilitédu plan- et j'étudie d'autre part son injectivité.Je montre que si le support d'une mesure de probabilité est assez gros, par exemple siil contient une boule ouvert, alors la limite que cette mesure engendre suffit à caractériser cette mesure à une transformation projective près.Un second chapitre traite de test de propriété.Un testeur de propriété est un algorithme aléatoire permettant de séparerles objets ayant une certaine propriété des objet à distance au moins εde l'avoir, au sens de la distance d'édition.Ce domaine donne des algorithmes extrêmement rapides, et en particulierdes algorithmes dont la complexité ne dépends pas de la taille de l'entréemais seulement du paramètre de précision ε.Un résultat fondamental de cet domaine pour les graphes montré par Alonet Shapira est le suivant : toute classe de graphe héréditaire possède un teltesteur.Cette thèse contribue à la question suivante :Quelles classes de graphes possède un testeur dont la complexité est unpolynôme en 1/ε ?Je montre qu'en particulier la classe des graphes d'intervales possède un teltesteur.La théorie des algèbres de drapeaux est un outil étroitement lié aux limites degraphes denses qui donne une méthode pour démontrer des bornes sur certainsparamètres combinatoires à l'aide d'un ordinateur.Dans un troisième chapitre, je présente un programme écrit durant ma thèsequi implémente cette méthode.Ce programme fonctionne comme une bibliothèque pour calculer dans les algèbresde drapeaux, manipuler des inégalités sur les drapeaux ou encoder des problèmesd'optimisations par une instance de programme semi-défini positif qui peutensuite être résolu par un solveur externe.Ce programme est en particulier utilisé pour obtenir un nouvelle borne pour le cas triangulaire de la conjecture de Caccetta-Häggkvist. / This thesis is focused on problems related to the theory of combinatorial limits.This theory opened links between different fields such asanalysis, combinatorics, geometry and probability theory.In this thesis, we apply ideas coming from this framework toproblems in extremal combinatorics.In a first chapter we develop a theory of limits for emph{order types},a geometrical object that encodes configuration of a set of points in theplane by the mean of the orientations of their triangles.The order type of a point set suffices to determine many of its properties,such as for instance the boundary of its convex hull.We show that the limit of a converging sequence of order typescan be represented by random-free object analogous to a graphon.Further, we link this notion to the natural distributions of order typesarising from the sampling of random points from some probability measureof the plane.We observe that in this mean, every probability measure gives rise to a limitof order types.We show that this map from probability measure on the plane to limit oforder type is not surjective.Concerning its injectivity,we prove that if a measure has large enough support, for instance if its supportcontains an open ball, the limit of order types the measure generatessuffices to essentially determine this measure.A second chapter is focused on property testing.A tester is a randomized algorithm for distinguishing between objects satisfyinga property from those that are at some distance at least εfrom having itby means of the edition distance.This gives very efficient algorithms, and in particular algorithms whosecomplexity does not depend on the size of the input but only on the parameter ε.For graphs, it has been shown by Alon and Shapira that every hereditary propertyhas such a tester.We contribute to the following question :which classes of graphs have a one-sided property tester with a number of queries that is a polynomial in 1/ε ?We give a proof that the class of interval graphs has such a tester.The theory of flag algebras is a framework introduced by Razborovclosely related to dense limit of graphs, that gives a way to systematicallyderive bounds for parameters in extremal combinatorics.In a third chapter we present a program developed during my Phd.that implements this method.This program works as a library that can compute flag algebras,manipulate inequalities on densities and encode the optimization of some parameterin a semi-definite positive instance that can be given to a dedicated solverto obtain a bound on this parameter.This program is in particular used to obtain a new bound forthe triangle case of the Caccetta-Häggkvist conjecture.

Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitative. / This thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory.

No description available.

With the publication of the famous Erdős-Ko-Rado Theorem in 1961, intersection problems became a popular area of combinatorics. A family of combinatorial objects is t-intersecting if any two of its elements mutually t-intersect, where the latter concept needs to be specified separately in each instance. This thesis is split into two parts; the first is concerned with intersecting injections while the second investigates intersecting posets. We classify maximum 1-intersecting families of injections from {1, ..., k} to {1, ..., n}, a generalisation of the corresponding result on permutations from the early 2000s. Moreover, we obtain classifications in the general t>1 case for different parameter limits: if n is large in terms of k and t, then the so-called fix-families, consisting of all injections which map some fixed set of t points to the same image points, are the only t-intersecting injection families of maximal size. By way of contrast, fixing the differences k-t and n-k while increasing k leads to optimal families which are equivalent to one of the so-called saturation families, consisting of all injections fixing at least r+t of the first 2r+t points, where r=|_ (k-t)/2 _|. Furthermore we demonstrate that, among injection families with t-intersecting and left-compressed fixed point sets, for some value of r the saturation family has maximal size . The concept that two posets intersect if they share a comparison is new. We begin by classifying maximum intersecting families in several isomorphism classes of posets which are linear, or almost linear. Then we study the union of the almost linear classes, and derive a bound for an intersecting family by adapting Katona's elegant cycle method to posets. The thesis ends with an investigation of the intersection structure of poset classes whose elements are close to the antichain. The overarching theme of this thesis is fixing versus saturation: we compare the sizes and structures of intersecting families obtained from these two distinct principles in the context of various classes of combinatorial objects.

The purpose of the dissertation is to prove universal tight bounds for deviation from the mean probability inequalities for functions of random variables. Universal bounds shows that they are uniform with respect to some class of distributions and quantity of variables and other parameters. The bounds are called tight, if we can construct a sequence of random variables, such that the upper bounds are achieved. Such inequalities are useful for example in insurance mathematics, for constructing effective algorithms. We extend the results for Lipschitz functions on general probability metric spaces. / Disertacijos darbo tikslas – įrodyti universalias tiksliąsias nelygybes atsitiktinių dydžių funkcijų nukrypimo nuo vidurkio tikimybėms. Universalios nelygybės pažymi, kad jos yra tolygios pagal tam tikras bendras skirstinių klases ir pagal atsitiktinių dydžių kiekį, kartais ir pagal kitus parametrus. Nelygybės vadinamos tiksliosiomis, jeigu pavyksta sukonstruoti atsitiktinių dydžių seką, kuriai nelygybės virsta lygybėmis. Tokios nelygybės labai naudingos, pavyzdžiui, draudimo matematikoje, konstruojant efektyvius algoritmus. Disertaciją sudaro šeši skyriai. Pirmasis skyrius yra įvadas, kuriame neformaliai pristatomas disertacijoje tiriamas objektas, pateikiamas bendras darbo aprašymas ir motyvacija. Detalesnė kitų autorių rezultatų apžvalga pateikiama atskirai kiekviename skyriuje. Antrasis skyrius skirtas atvejui, kai atsitiktiniai dydžiai yra aprėžti ir simetriniai. Trečiajame skyriuje įrodomos nelygybės atsitiktiniams dydžiams, tenkinantiems dispersijos aprėžtumo sąlygą. Ketvirtajame skyriuje nagrinėjamos sąlyginai aprėžtų atsitiktinių dydžių sumos. Penktajame skyriuje tiriamos atsitiktinių dydžių sekos, sudarančios martingalą arba supermartingalą, ir joms gaunamos universaliosios tikimybinės nelygybės ir sukonstruojama nehomogeninė Markovo grandinė, kuri yra martingalas, ir kuriai minėtos nelygybės virsta lygybėmis. Šeštajame skyriuje rezultatai yra apibendrinami atsitiktinių dydžių sekos Lipšico funkcijoms.

Disertacijos darbo tikslas – įrodyti universalias tiksliąsias nelygybes atsitiktinių dydžių funkcijų nukrypimo nuo vidurkio tikimybėms. Universalios nelygybės pažymi, kad jos yra tolygios pagal tam tikras bendras skirstinių klases ir pagal atsitiktinių dydžių kiekį, kartais ir pagal kitus parametrus. Nelygybės vadinamos tiksliosiomis, jeigu pavyksta sukonstruoti atsitiktinių dydžių seką, kuriai nelygybės virsta lygybėmis. Tokios nelygybės labai naudingos, pavyzdžiui, draudimo matematikoje, konstruojant efektyvius algoritmus. Disertaciją sudaro šeši skyriai. Pirmasis skyrius yra įvadas, kuriame neformaliai pristatomas disertacijoje tiriamas objektas, pateikiamas bendras darbo aprašymas ir motyvacija. Detalesnė kitų autorių rezultatų apžvalga pateikiama atskirai kiekviename skyriuje. Antrasis skyrius skirtas atvejui, kai atsitiktiniai dydžiai yra aprėžti ir simetriniai. Trečiajame skyriuje įrodomos nelygybės atsitiktiniams dydžiams, tenkinantiems dispersijos aprėžtumo sąlygą. Ketvirtajame skyriuje nagrinėjamos sąlyginai aprėžtų atsitiktinių dydžių sumos. Penktajame skyriuje tiriamos atsitiktinių dydžių sekos, sudarančios martingalą arba supermartingalą, ir joms gaunamos universaliosios tikimybinės nelygybės ir sukonstruojama nehomogeninė Markovo grandinė, kuri yra martingalas, ir kuriai minėtos nelygybės virsta lygybėmis. Šeštajame skyriuje rezultatai yra apibendrinami atsitiktinių dydžių sekos Lipšico funkcijoms. / The purpose of the dissertation is to prove universal tight bounds for deviation from the mean probability inequalities for functions of random variables. Universal bounds shows that they are uniform with respect to some class of distributions and quantity of variables and other parameters. The bounds are called tight, if we can construct a sequence of random variables, such that the upper bounds are achieved. Such inequalities are useful for example in insurance mathematics, for constructing effective algorithms. We extend the results for Lipschitz functions on general probability metric spaces.

In dieser Arbeit wird zuerst das Theorem von Chung, Graham und Wilson über quasi-zufällige Graphen zur sogenannten schwachen Quasi-Zufälligkeit für k-uniforme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaften bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen gefunden, welche die Quasi-Zufälligkeit für Graphen ``forcieren''''. Zuvor waren nur bipartite Graphen mit dieser Eigenschaft bekannt. Desweiteren ist ein konzeptionell einfacher Algorithmus zum Verifizieren nicht erfüllbarer zufälliger k-SAT Formeln angegeben. Dann richtet sich der Fokus auf Anwendungen verschiedener Regularitätslemmata für Hypergraphen. Zuerst wird die Menge aller bezeichneten 3-uniformen Hypergraphen auf n Knoten, die keine Kopie des Hypergraphen der Fano Ebene enthalten, studiert. Es wird gezeigt, dass fast jedes Element aus dieser Menge ein bipartiter Hypergraph ist. Dies führt zu einem Algorithmus, der in polynomiell erwarteter Zeit einen zufälligen Fano-freien (und somit einen zufälligen bipartiten 3-uniformen) Hypergraphen richtig färbt. Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben gegeben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann man die Kanten eines k-uniformen Hypergraphen H färben, so dass keine monochromatische Kopie von F entsteht? Welche Hypergraphen H maximieren die Anzahl erlaubter Kantenfärbungen? Hier wird ein strukturelles Resultat für eine natürliche Klasse von Hypergraphen bewiesen. Es wird für viele Hypergraphen F, deren extremaler Hypergraph bekannt ist, gezeigt, dass im Falle von zwei oder drei Farben die extremalen Hypergraphen die oben beschriebene Funktion maximieren, während für vier oder mehr Farben andere Hypergraphen mehr Kantenfärbungen zulassen. / This thesis presents first one possible generalization of the result of Chung, Graham and Wilson to k-uniform hypergraphs, and studies the so-called weak quasi-randomness. As applications we obtain a simple strong refutation algorithm for random sparse k-SAT formulas and we identify first non-bipartite forcing pairs for quasi-random graphs. Our focus then shifts from the study of quasi-random objects to applications of different versions of the hypergraph regularity lemmas; all these versions assert decompositions of hypergraphs into constantly many quasi-random parts, where the meaning of ``quasi-random'''' takes different contexts in different situations. We study the family of hypergraphs not containing the hypergraph of the Fano plane as a subhypergraph, and show that almost all members of this family are bipartite. As a consequence an algorithm for coloring bipartite 3-uniform hypergraphs with average polynomial running time is given. Then the following combinatorial extremal problem is considered. Suppose one is given r colors and a fixed hypergraph F. The question is: In at most how many ways can one color the hyperedges of a hypergraph H on n vertices such that no monochromatic copy of F is created? What are the extremal hypergraphs for this function? Here a structural result for a natural family of hypergraphs F is proven. For some special classes of hypergraphs we show that their extremal hypergraphs (for large n) maximize the number of edge colorings for 2 and 3 colors, while for at least 4 colors other hypergraphs are optimal.