Name
Abstract | ||
|---|---|---|
For positive integers k and l, a k-uniform hypergraph is called a loose path of length l, and denoted by P-l((k)), if its vertex set is {v(1), v(2), ..., v((k-1)l+1)} and the edge set is {e(i) = {v((i-1)(k-1)+q) : 1 <= q <= k}, i = 1, ..., l}, that is, each pair of consecutive edges intersects on a single vertex. Let R(P-l((k)); r) be the multicolor Ramsey number of a loose path that is the minimum n such that every r-edge-coloring of the complete k-uniform hypergraph K-n((k)) yields a monochromatic copy of P-l((k)). In this note we are interested in constructive upper bounds on R(P-l((k)); r) which means that on the cost of possibly enlarging the order of the complete hypergraph, we would like to efficiently find a monochromatic copy of P-l((k)) in every coloring. In particular, we show that there is a constant c > 0 such that for all k >= 2, l >= 3, 2 <= r <= k - 1, and n >= k(l + 1) r(1 + ln(r)), there is an algorithm such that for every r-edge-coloring of the edges of K-n((k)), it finds a monochromatic copy of P-l((k)) in time at most cn(k) |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-77404-6_31 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Computer science,Hypergraph,Ramsey's theorem | Conference | 10807 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Andrzej Rucinski | 2 | 0 | 1.01 |