2013 | OriginalPaper | Chapter
An Unstable Hypergraph Problem with a Unique Optimal Solution
Authors : Carlos Hoppen, Yoshiharu Kohayakawa, Hanno Lefmann
Published in: Information Theory, Combinatorics, and Search Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
There is a variety of problems in extremal combinatorics for which there is a unique configuration achieving the optimum value. Moreover, as the size of the problem grows, configurations that “almost achieve” the optimal value can be shown to be “almost equal” to the extremal configuration. This phenomenon, known as
stability
, has been formalized by Simonovits [A Method for Solving Extremal Problems in Graph Theory, Stability Problems,
Theory of Graphs
(Proc.Colloq., Tihany, 1966), 279–319] in the context of graphs, but has since been considered for several combinatorial structures. In this work, we describe a hypergraph extremal problem with an unusual combinatorial feature, namely, while the problem is unstable, it has a unique optimal solution up to isomorphism. To the best of our knowledge, this is the first such example in the context of (simple) hypergraphs.
More precisely, for fixed positive integers
r
and ℓ with 1 ≤ ℓ <
r
, and given an
r
-uniform hypergraph
H
, let
κ
(
H
, 4,ℓ) denote the number of 4-colorings of the set of hyperedges of
H
for which any two hyperedges in the same color class intersect in at least ℓ elements. Consider the function KC
$(n,r,4,\ell)=\max_{H\in{\mathcal H}_{n,r}} \kappa (H, 4,\ell) $
, where the maximum runs over the family
${\mathcal H}_{n,r}$
of all
r
-uniform hypergraphs on
n
vertices. We show that, for
n
large, there is a unique
n
-vertex hypergraph
H
for which
κ
(
H
, 4,ℓ) = KC(
n
,
r
,4,ℓ), despite the fact that the problem of determining KC(
n
,
r
,4,ℓ) is unstable for every fixed
r
> ℓ ≥ 2.