COMBINATORICS 1.3 COMBINATORICS A hypergraph is a pair H=(V,E).where V is a finite set whose elements are called vertices and E is a family of subsets of V,called edges.It is n-uniform if each of its edges contains precisely n vertices.We say that H has property B,or that it is two-colorable if there is a two-coloring of V such that no edge is monochromatic Letm()denote the minimum of that does not have property B. Proposition 1.3.1 [Erdos(1963a)]Every n-uniform hypergraph with less than 2n- edges has property B.Therefore m(n) Proof.LetH-(V,E)be an n-unform hypergraph with less than -edges monochomaie P Color V randomly by two colors.For edge e E.let A.be the event that e is Therefore Pr V Ae≤∑Pr[Ac]<I eEe and there is a two-coloring without monochromatic edges. ◆ In Section 3.5 we present a more delicate argument,due to Radhakrishnan and Srinivasan,and based on an idea of Beck,that shows that m≥n()' The best known upper bound to m(n)is found by turing the probabilistic argu- ment"on its head."Basically,the sets become random and each coloring defines an event.Fix V with v points,where we shall later optimize v.Let x be a coloring of V poins inone color,a points in the other.Let SVbean Pr[S is moncchromatic underx) ( Let us assume v is even for convenience.As (is convex,this expression is minimized when a=b.Thus Pr'S is monochromatic under x>p, where we set p=(COMBINATORIOS 7 1.3 COMBINATORIOS A hypergraph is a pair H = (V,E), where V is a finite set whose elements are called vértices and E is a family of subsets of V, called edges. It is n-uniform if each of its edges contains precisely n vértices. We say that H has property B, or that it is two-colorable if there is a two-coloring of y such that no edge is monochromatic. Let m{n) denote the minimum possible number of edges of an n-uniform hypergraph that does not have property B. Proposition 1.3.1 [Erdos (1963a)] Every n-uniform hypergraph with less than 2n ~ l edges has property B. Therefore m(n) > 2n ~ 1 . Proof. Let H = (V,E) be an n-uniform hypergraph with less than 2 n _ 1 edges. Color V randomly by two colors. For each edge e e E, let Ae be the event that e is monochromatic. Clearly Pr [Ae] = 21_Tl . Therefore Pr \J Ae .eeE <£Pr[Ae ] <l eeE and there is a two-coloring without monochromatic edges. • In Section 3.5 we present a more delicate argument, due to Radhakrishnan and Srinivasan, and based on an idea of Beck, that shows that / / n \ J / 2 The best known upper bound to m(n) is found by turning the probabilistic argu￾ment "on its head." Basically, the sets become random and each coloring defines an event. Fix V with v points, where we shall later optimize v. Let x be a coloring of V with a points in one color, b — v — a points in the other. Let S c V be a uniformly selected n-set. Then ( a ) + H Pr [S is monochromatic under x] = /v\ • \n) Let us assume v is even for convenience. As (JQ is convex, this expression is minimized when a = b. Thus Pr [S is monochromatic under x] > P > where we set p o