Search for: All records

Abstract A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary$$r$$-colouring of the complete$$k$$-uniform hypergraph$$K_n^k$$when$$k\geq 2$$and$$k\in \{r-1,r\}$$. We prove a result which says that if one replaces$$K_n^k$$in Gyárfás’ theorem by any ‘expansive’$$k$$-uniform hypergraph on$$n$$vertices (that is, a$$k$$-uniform hypergraph$$G$$on$$n$$vertices in which$$e(V_1, \ldots, V_k)\gt 0$$for all disjoint sets$$V_1, \ldots, V_k\subseteq V(G)$$with$$|V_i|\gt \alpha$$for all$$i\in [k]$$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on$$r$$and$$\alpha$$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary$$r$$-partite$$r$$-uniform hypergraph$$H$$with$$n$$edges in which every set of$$k$$edges has a common intersection. In this language, our result says that if one replaces the condition that every set of$$k$$edges has a common intersection with the condition that for every collection of$$k$$disjoint sets$$E_1, \ldots, E_k\subseteq E(H)$$with$$|E_i|\gt \alpha$$, there exists$$(e_1, \ldots, e_k)\in E_1\times \cdots \times E_k$$such that$$e_1\cap \cdots \cap e_k\neq \emptyset$$, then the smallest possible maximum degree of$$H$$is essentially the same (within a small error term depending on$$r$$and$$\alpha$$). We prove our results in this dual setting. 

Abstract A result of Gyárfás says that for every 3‐coloring of the edges of the complete graph , there is a monochromatic component of order at least , and this is best possible when 4 divides . Furthermore, for all and every ‐coloring of the edges of the complete ‐uniform hypergraph , there is a monochromatic component of order at least and this is best possible for all . Recently, Guggiari and Scott and independently Rahimi proved a strengthening of the graph case in the result above which says that the same conclusion holds if is replaced by any graph on vertices with minimum degree at least ; furthermore, this bound on the minimum degree is best possible. We prove a strengthening of the case in the result above which says that the same conclusion holds if is replaced by any ‐uniform hypergraph on vertices with minimum ‐degree at least ; furthermore, this bound on the ‐degree is best possible. 

We prove that for all graphs with at most $(3.75-o(1))n$ edges there exists a 2-coloring of the edges such that every monochromatic path has order less than $$n$$.  This was previously known to be true for graphs with at most $2.5n-7.5$ edges. We also improve on the best-known lower bounds in the $$r$$-color case.