Timeline for Strongly minimal covers for clique hypergraphs of graphs
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 17, 2022 at 12:52 | comment | added | Tri | @domotorp Thanks. I will try to see the connection between the Erdos-Hajnal paper and this question. (I vaguely recall that Shelah showed something funny happens at $\aleph_{\omega+1}$.) | |
| May 17, 2022 at 8:11 | comment | added | domotorp | If instead of $G$, you consider $\bar G$, then a cover becomes a proper coloring, and the strongly minimal condition translates to that no union of some color classes can be recolored with fewer colors. I think it's a good idea to look at some old papers dealing with similar constructions, like renyi.hu/~p_erdos/1968-04.pdf. | |
| May 15, 2022 at 18:36 | comment | added | bof | (I) Let $G$ be a graph and let $f:V(G)\to\mathbb N$ be a proper coloring of $G$. Suppose that, for each $n\in\mathbb N$, there is an induced subgraph $G_n$ of $G$ such that $\chi(G_n)=n$ and $f[V(G_n)]=\{1,2,\dots n\}$. Then the color classes of $f$ are a strongly minimal cover of $V$ by anticliques. (II) If $G$ is a locally finite graph with infinite chromatic number, then such a coloring $f$ can be constructed. @Tri | |
| May 15, 2022 at 11:01 | comment | added | Tri | @bof I think Dominic van der Zypen means (at least, I mean): What is the proof? I'm guessing it is some application of something like Rado's Selection Lemma. | |
| May 15, 2022 at 7:50 | comment | added | Dominic van der Zypen | Can you clarify your comment @bof? | |
| May 15, 2022 at 6:55 | answer | added | domotorp | timeline score: 1 | |
| May 14, 2022 at 23:54 | comment | added | Tri | Thank you. I'll have to think about why it's clear. ;-) | |
| May 14, 2022 at 20:54 | comment | added | bof | You are asking whether every graph has a strongly minimal covering by cliques. An equivalent (perhaps more natural) question is whether every graph has a strongly minimal cover by anticliques (independent sets). It seems clear that every locally finite graph has a strongly minimal cover by anticliques. | |
| May 14, 2022 at 17:36 | comment | added | Tri | I have edited the definition of "cover." Thanks. | |
| May 14, 2022 at 17:35 | history | edited | Tri | CC BY-SA 4.0 |
added 112 characters in body
|
| May 14, 2022 at 9:47 | comment | added | Mikhail Tikhomirov | I assume "a family $C$ of subsets of $F$" means a collection of hyperedges, rather than a collection of hyperedge sets ("subsets of $F$")? | |
| May 14, 2022 at 5:33 | history | edited | YCor | CC BY-SA 4.0 |
formatting, added tag
|
| May 14, 2022 at 4:52 | history | asked | Tri | CC BY-SA 4.0 |