On Colorings of 3-Homogeneous Hypergraphs in 3 Colors
- PDF / 263,349 Bytes
- 14 Pages / 594 x 792 pts Page_size
- 67 Downloads / 178 Views
ON COLORINGS OF 3-HOMOGENEOUS HYPERGRAPHS IN 3 COLORS I. A. Akolzin
UDC 519.17
Abstract. In this paper, we examine the value m(n, r) in the Erd˝ os–Hajnal problem. Using various methods, we obtain the estimate 27 ≤ m(3, 3) ≤ 35. Keywords and phrases: hypergraph, coloring, combinatorics. AMS Subject Classification: 05D99
1. Basic definitions. In this paper, we study a classical problem of extremal combinatorics, namely, the Erd˝os–Hajnal problem about the coloring of hypergraphs. First, we recall basic definitions from the theory of hypergraphs. A hypergraph is a pair H = (V, E), where V is a set (as a rule, finite) called the set of vertices of the hypergraph, and E = E(H) is an arbitrary collection of subsets of the set V called edges of a hypergraph. The hypergraph H is said to be n-homogeneous if each edge contains exactly n vertices. In particular, an ordinary graph without loops, multiple edges, and orientation is a 2-homogeneous hypergraph. The degree of a vertex is the number of edges incident to this vertex. A coloring of the set of vertices of a hypergraph H = (V, E) is a mapping χ : V → N. We say that an edge e ∈ E is monochrome in χ if for all u, v ∈ e, we have χ(u) = χ(v). We say that an edge e represents a coloring χ if it is monochrome in χ. A coloring is called a regular coloring of vertices of a hypergraph if each edge in this hypergraph is not monochrome. The chromatic number χ(H) of a hypergraph H is the minimum number of colors required for a regular coloring of vertices of H. A maximal independent set of a hypergraph H is a subset of vertices of the maximal possible cardinality, which does not contain any edge of the hypergraph. Any such sets is denoted by A(H) and its cardinality by |A(H)| = α(H). 2.
Erd˝ os–Hajnal problem.
2.1. Statement of the problem. One of the key problems of the theory of hypergraph coloring is the classical Erd˝ os–Hajnal problem (see [6]). It is formulated as follows: find the minimal possible number m(n) of edges of a hypergraph in the class of n-homogeneous hypergraphs with chromatic number greater than 2. Formally, the definition of m(n) can be written as follows: m(n) = min |E(H)| : H is an n-homogenous hypergraph, χ(H) > 2 . (1) It is easy to verify that m(n) is finite and satisfies the inequality 2n − 1 m(n) ≤ . n
(2)
This relation is obtained by taking a set of vertices of cardinality 2n − 1 and the set of all its n-subsets as the set of edges. Clearly, in any two-color coloring of the set of vertices, there exists an n-element monochrome subset. Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory, Vol. 150, Geometry and Mechanics, 2018. c 2020 Springer Science+Business Media, LLC 1072–3374/20/2506–0881
881
The problem can be naturally generalized to the case of an arbitrary number of colors. We introduce the number m(n, r) as follows: m(n, r) = min |E(H)| : H is an n-homogenous hypergraph, χ(H) > r . (3) This definition implies that m(n, 2) = m(n). As well as m(n), the number m(n, r) is
Data Loading...
