Skip to main content
inserted correct link, provided by Sam Hopkins
Source Link

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap A_i \neq \emptyset$ for all $i\in I$. See Conjecture 10.1 in this articlethis article by Ron Aharoni and Eli Berger.

Interestingly, this conjecture is implied by the following covering problem in hypergraphs: Let $H=(V,E)$ be a hypergraph with the following properties:

  1. $\bigcup E = V$,
  2. Any subset of $e\in E$ is a member of $E$, and
  3. whenever $S\subseteq V$ and every $2$-element subset of $S$ belongs to $E$, then $S\in E$.

Then there is $J\subseteq E$ such that whenever $K\subseteq E$ has the property that $\bigcup K = V$ then $|J\setminus K| \leq |K\setminus J|$. (In that case $J$ is said to be a "strongly minimal cover" because it covers $V$ "more efficiently" in some sense, than any other cover.)

This covering problem is mentioned in Conjecture 10.3.(2) of the same paper.

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap A_i \neq \emptyset$ for all $i\in I$. See Conjecture 10.1 in this article by Ron Aharoni and Eli Berger.

Interestingly, this conjecture is implied by the following covering problem in hypergraphs: Let $H=(V,E)$ be a hypergraph with the following properties:

  1. $\bigcup E = V$,
  2. Any subset of $e\in E$ is a member of $E$, and
  3. whenever $S\subseteq V$ and every $2$-element subset of $S$ belongs to $E$, then $S\in E$.

Then there is $J\subseteq E$ such that whenever $K\subseteq E$ has the property that $\bigcup K = V$ then $|J\setminus K| \leq |K\setminus J|$. (In that case $J$ is said to be a "strongly minimal cover" because it covers $V$ "more efficiently" in some sense, than any other cover.)

This covering problem is mentioned in Conjecture 10.3.(2) of the same paper.

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap A_i \neq \emptyset$ for all $i\in I$. See Conjecture 10.1 in this article by Ron Aharoni and Eli Berger.

Interestingly, this conjecture is implied by the following covering problem in hypergraphs: Let $H=(V,E)$ be a hypergraph with the following properties:

  1. $\bigcup E = V$,
  2. Any subset of $e\in E$ is a member of $E$, and
  3. whenever $S\subseteq V$ and every $2$-element subset of $S$ belongs to $E$, then $S\in E$.

Then there is $J\subseteq E$ such that whenever $K\subseteq E$ has the property that $\bigcup K = V$ then $|J\setminus K| \leq |K\setminus J|$. (In that case $J$ is said to be a "strongly minimal cover" because it covers $V$ "more efficiently" in some sense, than any other cover.)

This covering problem is mentioned in Conjecture 10.3.(2) of the same paper.

Source Link

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap A_i \neq \emptyset$ for all $i\in I$. See Conjecture 10.1 in this article by Ron Aharoni and Eli Berger.

Interestingly, this conjecture is implied by the following covering problem in hypergraphs: Let $H=(V,E)$ be a hypergraph with the following properties:

  1. $\bigcup E = V$,
  2. Any subset of $e\in E$ is a member of $E$, and
  3. whenever $S\subseteq V$ and every $2$-element subset of $S$ belongs to $E$, then $S\in E$.

Then there is $J\subseteq E$ such that whenever $K\subseteq E$ has the property that $\bigcup K = V$ then $|J\setminus K| \leq |K\setminus J|$. (In that case $J$ is said to be a "strongly minimal cover" because it covers $V$ "more efficiently" in some sense, than any other cover.)

This covering problem is mentioned in Conjecture 10.3.(2) of the same paper.

Post Made Community Wiki by Dominic van der Zypen