Countable version of Erdös-Lovasz-Faber conjecture
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
Let $X$ be an infinite set, and let $(A_n)_ninomega$ be a collection of subsets of $X$ with the following properties:
- $|A_mcap A_n| leq 1$ for $mneq nin omega$, and
- $|A_n|=aleph_0$ for all $nin omega$.
We consider the following statement:
(EFL$_omega$:) There is $f:Xto omega$ such that for all $ninomega$ the restriction $f|_A_n:A_ntoomega$ is a bijection.
Questions. Is (EFL$_omega$) true? Or does (EFL$_omega$) imply the original Erdös-Faber-Lovasz conjecture?
co.combinatorics graph-theory graph-colorings infinite-combinatorics erdos
add a comment |Â
up vote
5
down vote
favorite
Let $X$ be an infinite set, and let $(A_n)_ninomega$ be a collection of subsets of $X$ with the following properties:
- $|A_mcap A_n| leq 1$ for $mneq nin omega$, and
- $|A_n|=aleph_0$ for all $nin omega$.
We consider the following statement:
(EFL$_omega$:) There is $f:Xto omega$ such that for all $ninomega$ the restriction $f|_A_n:A_ntoomega$ is a bijection.
Questions. Is (EFL$_omega$) true? Or does (EFL$_omega$) imply the original Erdös-Faber-Lovasz conjecture?
co.combinatorics graph-theory graph-colorings infinite-combinatorics erdos
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Let $X$ be an infinite set, and let $(A_n)_ninomega$ be a collection of subsets of $X$ with the following properties:
- $|A_mcap A_n| leq 1$ for $mneq nin omega$, and
- $|A_n|=aleph_0$ for all $nin omega$.
We consider the following statement:
(EFL$_omega$:) There is $f:Xto omega$ such that for all $ninomega$ the restriction $f|_A_n:A_ntoomega$ is a bijection.
Questions. Is (EFL$_omega$) true? Or does (EFL$_omega$) imply the original Erdös-Faber-Lovasz conjecture?
co.combinatorics graph-theory graph-colorings infinite-combinatorics erdos
Let $X$ be an infinite set, and let $(A_n)_ninomega$ be a collection of subsets of $X$ with the following properties:
- $|A_mcap A_n| leq 1$ for $mneq nin omega$, and
- $|A_n|=aleph_0$ for all $nin omega$.
We consider the following statement:
(EFL$_omega$:) There is $f:Xto omega$ such that for all $ninomega$ the restriction $f|_A_n:A_ntoomega$ is a bijection.
Questions. Is (EFL$_omega$) true? Or does (EFL$_omega$) imply the original Erdös-Faber-Lovasz conjecture?
co.combinatorics graph-theory graph-colorings infinite-combinatorics erdos
co.combinatorics graph-theory graph-colorings infinite-combinatorics erdos
asked Sep 5 at 6:00
Dominic van der Zypen
12.9k43170
12.9k43170
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
7
down vote
accepted
If I understand it correctly, it's false. Let $x notin A_0 = 1,2,dots $. Then let $A_i$ all meet at $x$, and also each meet $A$ at $i$ (add extra elements as necessary; they should be irrelevant). Then $f(x) neq f(i)$ for any $i$, so $f(x) notin f(A)$.
This didn't work in the finite case because the sets meeting $A$ cannot exhaust $A$, as the number of such sets is strictly less than the number of elements of $A$. When working over infinite sets, this is no longer true.
1
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
accepted
If I understand it correctly, it's false. Let $x notin A_0 = 1,2,dots $. Then let $A_i$ all meet at $x$, and also each meet $A$ at $i$ (add extra elements as necessary; they should be irrelevant). Then $f(x) neq f(i)$ for any $i$, so $f(x) notin f(A)$.
This didn't work in the finite case because the sets meeting $A$ cannot exhaust $A$, as the number of such sets is strictly less than the number of elements of $A$. When working over infinite sets, this is no longer true.
1
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
add a comment |Â
up vote
7
down vote
accepted
If I understand it correctly, it's false. Let $x notin A_0 = 1,2,dots $. Then let $A_i$ all meet at $x$, and also each meet $A$ at $i$ (add extra elements as necessary; they should be irrelevant). Then $f(x) neq f(i)$ for any $i$, so $f(x) notin f(A)$.
This didn't work in the finite case because the sets meeting $A$ cannot exhaust $A$, as the number of such sets is strictly less than the number of elements of $A$. When working over infinite sets, this is no longer true.
1
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
add a comment |Â
up vote
7
down vote
accepted
up vote
7
down vote
accepted
If I understand it correctly, it's false. Let $x notin A_0 = 1,2,dots $. Then let $A_i$ all meet at $x$, and also each meet $A$ at $i$ (add extra elements as necessary; they should be irrelevant). Then $f(x) neq f(i)$ for any $i$, so $f(x) notin f(A)$.
This didn't work in the finite case because the sets meeting $A$ cannot exhaust $A$, as the number of such sets is strictly less than the number of elements of $A$. When working over infinite sets, this is no longer true.
If I understand it correctly, it's false. Let $x notin A_0 = 1,2,dots $. Then let $A_i$ all meet at $x$, and also each meet $A$ at $i$ (add extra elements as necessary; they should be irrelevant). Then $f(x) neq f(i)$ for any $i$, so $f(x) notin f(A)$.
This didn't work in the finite case because the sets meeting $A$ cannot exhaust $A$, as the number of such sets is strictly less than the number of elements of $A$. When working over infinite sets, this is no longer true.
edited Sep 5 at 6:35
answered Sep 5 at 6:28
user44191
2,059720
2,059720
1
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
add a comment |Â
1
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
1
1
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?)
â Dominic van der Zypen
Sep 5 at 8:04
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f309901%2fcountable-version-of-erd%25c3%25b6s-lovasz-faber-conjecture%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password