Essays in extremal combinatorics.

摘要

This dissertation addresses some problems in extremal combinatorics. The methods involve linear algebraic and probabilistic methods. Part I contains an introduction and definitions.; In Chapter 3 (Part II), we prove generalizations of the nonuniform modular RW theorem and of a theorem by P. Frankl and R. M. Wilson for pairs of set systems. The proofs are based on linear algebra techniques.; Chapter 4 contains a new proof of an old conjecture by P. Erdos asking for a maximal size of a family of subsets of an n-element set with forbidden intersection of size {dollar}lfloor n/4rfloor.{dollar} In fact, we prove a more general statement. Namely, let {dollar}rho{dollar} be a real number satisfying {dollar}00{dollar} such that for any two families {dollar}{lcub}cal F{rcub}{dollar} and {dollar}{lcub}cal G{rcub}{dollar} of subsets of an n-element set with the forbidden intersection {dollar}lfloorrho nrfloor,{dollar} one gets {dollar}vert{lcub}cal F{rcub}Vert{lcub}cal G{rcub}vertle(4-epsilon)sp{lcub}n{rcub}.{dollar}; Part III contains results on the maximal size of a family without a weak {dollar}Delta{dollar}-system, on the existence of uniformly intersecting subfamilies in set systems, and on the random greedy algorithm for asymptotic packings.; In the first chapter of Part III (Chapter 5), we show a new lower bound on the maximal size of a family without a weak {dollar}Delta{dollar}-system. Let {dollar}rge 3{dollar} be an integer. We show that for n being an even power of a prime there is a family {dollar}cal F{dollar} of subsets of an n-element set such that {dollar}cal F{dollar} does not contain a weak {dollar}r Delta{dollar}-system and with {dollar}vert{lcub}cal F{rcub}vertge 2sp{lcub}0.99cdotlog(r-1)cdot nsp{lcub}1/6{rcub}loglog n{rcub}.{dollar}; In Chapter 6, we prove a result on the size of uniformly intersecting subfamilies of pairs of two intersecting set systems. These can be also formulated as Ramsey-type results for set systems. Also, we give a similar result for matrices over an ordered ring.; The last chapter (Chapter 7) of the thesis deals with the random greedy algorithm for asymptotic packings in a certain class of uniform hypergraphs. It is shown that the random greedy algorithm yields almost surely an asymptotic packing for this class of hypergraphs. We also prove that a packing obtained by the "nibble" approach and by the random greedy algorithm will be essentially the same. Based on our analysis, we determine the number of edges that will be almost surely considered by the random greedy algorithm. Let {dollar}Tsb{lcub}alpha{rcub}{dollar} be the number of edges that the random greedy algorithm has to consider before yielding a packing of size {dollar}lceil{lcub}{lcub}n{rcub}over{lcub}r{rcub}{rcub}{lcub}cdot{rcub}(1-alpha)rceil.{dollar} We show that almost surely {dollar}Tsb{lcub}alpha{rcub}sim({lcub}{lcub}1{rcub}over{lcub}alpha{rcub}{rcub})sp{lcub}r-1{rcub}{lcub}cdot{rcub}{lcub}{lcub}n{rcub}over{lcub}r(r-1){rcub}{rcub}{dollar} as {dollar}alphato 0sp+{dollar} holds.