An official website of the United States government
Gyárfas proved that every coloring of the edges of $$K_n$$ with $t+1$ colors contains a monochromatic connected component of size at least $n/t$. Later, Gyárfás and Sárközy asked for which values of $$\gamma=\gamma(t)$$ does the following strengthening for almost complete graphs hold: if $$G$$ is an $$n$$-vertex graph with minimum degree at least $$(1-\gamma)n$$, then every $(t+1)$-edge coloring of $$G$$ contains a monochromatic component of size at least $n/t$. We show $$\gamma= 1/(6t^3)$$ suffices, improving a result of DeBiasio, Krueger, and Sárközy.
more »
« less
Large monochromatic components in hypergraphs with large minimum codegree
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.
more »
« less
- Award ID(s):
- 1954170
- PAR ID:
- 10468270
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- ISSN:
- 0364-9024
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
For an $$r$$-uniform hypergraph $$H$$, let $$\nu^{(m)}(H)$$ denote the maximum size of a set $$M$$ of edges in $$H$$ such that every two edges in $$M$$ intersect in less than $$m$$ vertices, and let $$\tau^{(m)}(H)$$ denote the minimum size of a collection $$C$$ of $$m$$-sets of vertices such that every edge in $$H$$ contains an element of $$C$$. The fractional analogues of these parameters are denoted by $$\nu^{*(m)}(H)$$ and $$\tau^{*(m)}(H)$$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$$. In this paper we prove bounds on the ratio between the parameters $$\tau^{(m)}$$ and $$\nu^{(m)}$$, and their fractional analogues. Our main result is that, for every $$r$$-uniform hypergraph~$$H$$,\[ \tau^{*(r-1)}(H)/\nu^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $$r-1$.We also prove that, for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$$, where the Turán number $$\operatorname{ex}_r(n, k)$$ is the maximum number of edges in an $$r$$-uniform hypergraph on $$n$$ vertices that does not contain a copy of the complete $$r$$-uniform hypergraph on $$k$$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$.more » « less
-
Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $$G = {\mathbb{F}}_2^n$$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.more » « less
-
Abstract Let denote the complete 3‐uniform hypergraph on vertices and the 3‐uniform hypergraph on vertices consisting of all edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off‐diagonal Ramsey number exhibits an unusual intermediate growth rate, namely,for some positive constants and . The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum such that any 2‐edge‐coloring of the Cartesian product contains either a red rectangle or a blue ?more » « less
-
For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾_𝑁 receives a set of 𝑠 colors from a palette of 𝑟 colors, then there is guaranteed to be a monochromatic clique on 𝑛 vertices, that is, a subset of 𝑛 vertices where all of the edges between them receive a common color. In particular, the case 𝑠 = 1 corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on 𝑅(𝑛; 𝑟, 𝑠) which imply that 𝑅(𝑛; 𝑟, 𝑠) = 2^Θ(𝑛𝑟) if 𝑠/𝑟 is bounded away from 0 and 1. The upper bound extends an old result of Erdős and Szemerédi, who treated the case 𝑠 = 𝑟 − 1, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.more » « less
