Approximations to m‐Colored Complete Infinite Hypergraphs |
| |
Authors: | Teeradej Kittipassorn Bhargav P. Narayanan |
| |
Affiliation: | 1. DEPARTMENT OF MATHEMATICAL SCIENCES, UNIVERSITY OF MEMPHIS, MEMPHIS;2. DEPARTMENT OF PURE MATHEMATICS AND MATHEMATICAL STATISTICS, UNIVERSITY OF CAMBRIDGE, CAMBRIDGE, UNITED KINGDOM |
| |
Abstract: | Given an edge coloring of a graph with a set of m colors, we say that the graph is exactly m‐colored if each of the colors is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number and for all sufficiently large k, there is a k‐coloring of the complete graph on such that no complete infinite subgraph is exactly m‐colored. In the light of this result, we consider the question of how close we can come to finding an exactly m‐colored complete infinite subgraph. We show that for a natural number m and any finite coloring of the edges of the complete graph on with m or more colors, there is an exactly ‐colored complete infinite subgraph for some satisfying ; this is best possible up to the additive constant. We also obtain analogous results for this problem in the setting of r‐uniform hypergraphs. Along the way, we also prove a recent conjecture of the second author and investigate generalizations of this conjecture to r‐uniform hypergraphs. |
| |
Keywords: | subjclass[2010]Primary 05D10 Secondary 05C63 05C65 |
|
|