2
$\begingroup$

Motivation. Every hypergraph $(\omega, E)$ where $E$ is countable and consists of infinite sets has property $\newcommand{\B}{\mathbf{B}}\B$. On the other hand, if the members of $E$ are allowed to be finite, it is easy to construct hypergraphs $(\omega,E)$ without property $\B$. I am interested in settings with finite edges where $\B$ holds. Let's make this precise.

Formalization. A hypergraph $H=(V,E)$ is said to have property $\B$ if there is $B\subseteq V$ such that $$e\cap B\neq\emptyset\neq e\setminus B$$ for all $e\in E$ with $|e|>1$.

A $\B$-function is a map $f:\omega\to (\omega\setminus \{0\})$ such that

whenever $E$ is a countable collection of finite subsets of $\omega$ and $\varphi:\omega\to E$ is a bijection with $$|\varphi(n)|=f(n)$$ for all $n\in\omega$, the hypergraph $(\omega, E)$ has property $\B$.

Question. In the comments below, Andreas Blass finds a $\B$-function. Is there a $\B$-function $f_0:\omega\to(\omega\setminus\{0\})$ such that for every $\B$-function $f$ we have $f_0(n)\leq f(n)$ for all $n\in\omega$?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Well, $f(n)=2n+2$ seems to work for the same reason as in te case of infinite hyperedges. Just go through the hyperedges one at a time, choosing two new elements from each --- one to go into $B$ and one to stay outside $B$. $2n+2$ ensures that, when you get to hyperedge $\varphi(n)$, you can choose two new (i.e., not previously chosen) elements, since the $n$ prior steps chose only $2n$ elements. $\endgroup$
    – Andreas Blass
    Commented Jul 23 at 18:25
  • $\begingroup$ Ok thanks I overlooked this. Is there a smallest B-function? Will rephrase question $\endgroup$
    – Dominic van der Zypen
    Commented Jul 23 at 19:21
  • 1
    $\begingroup$ I don't know about a smallest $f$, but my previous $f$ can be improved to $\max(n+1,2)$ with no added work. When you get to $\varphi(n)$, check which of its elements were chosen previously. If some went into $B$ and some out, then you don't need to do anything for $\varphi(n)$. If some went in and none out (or vice versa), then there are at most $n$ of them, so there's at least one unchosen one, and you only need to choose one. And if none have been previously chosen, then you need two and you have at least two. $\endgroup$
    – Andreas Blass
    Commented Jul 23 at 19:49
  • 1
    $\begingroup$ Note that my constructions are "online" in the sense that, when working on $\varphi(n)$, you use information only about the sets $\varphi(k)$ for $k\leq n$. I don't see a way to do better than $\max(n+1,2)$ online, but I have no good idea about what might be possible by looking ahhead, to larger $k$. $\endgroup$
    – Andreas Blass
    Commented Jul 23 at 19:53
  • $\begingroup$ Thank you to both Andreas and bof. Can you post your comment as an answer, bof? $\endgroup$
    – Dominic van der Zypen
    Commented Jul 23 at 22:40

1 Answer 1

Reset to default
6
$\begingroup$

The question is really about finite hypergraphs, seeing as an infinite hypergraph (with finite edges) is $2$-colorable (i.e., has property B) iff every finite subhypergraph is $2$-colorable. In effect you are asking about which finite multisets of integers $\ge2$ can be realized as the multiset of edge-sizes of a hypergraph which does not have property B. This is a well-considered question, at least for uniform multisets; see Karl Grill and Daniel Linzmayer, Improved lower bounds for property B (arxiv).

Since a rearrangement of a B-function is a B-function, you probably want to restrict your question to nondecreasing B-functions. Even with this restriction there is no smallest B-function, in view of the following.

The sequence $f=(3,3,3,3,3,6,7,8,9,\dots)$ is a B-function, in view of the fact that $m(3)\gt5$ where $m(n)$ is the minimum number of edges in an $n$-uniform hypergraph which does not have property B. (In fact $m(3)=7$; the smallest $3$-uniform hypergraph without property B is the Fano plane.) The sequence $g=(2,2,3,4,5,6,7,8,9,\dots)$ is also a B-function. However, the sequence $\min(f,g)=(2,2,3,3,3,6,7,8,9,\dots)$ is not a B-function, since the hypergraph with edges $\{1,2\}$, $\{1,3\}$, $\{2,3,4\}$, $\{2,3,5\}$, $\{1,4,5\}$ does not have property B.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .