Timeline for What properties do graphs avoiding large regular subgraphs have?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2023 at 17:33 | comment | added | Naysh | Oh, are those results for the existence of any (possibly very small) k-regular subgraph? | |
| Oct 6, 2023 at 14:57 | comment | added | dbal | FYI, the results above are not about spanning subgraphs | |
| Oct 6, 2023 at 14:50 | comment | added | Naysh | I have not, thanks for the references! It seems like these papers show that already avoiding an $r$-regular subgraph on $n$ nodes implies the graph is quite sparse. I would interested in seeing if the even stronger condition (suggested from my post) of avoiding an $r$-regular subgraph even on any subset of at least $n/3$ nodes (for example) implies some stronger results. | |
| Oct 5, 2023 at 18:58 | comment | added | dbal | Have you seen this paper? people.math.ethz.ch/~sudakovb/regular-subgraphs-of-graphs.pdf May be useful. More relevant perhaps Pyber, Rodl, Szemeredi core.ac.uk/download/pdf/81119371.pdf where they prove there are graphs with cnloglogn edges and no r-reg subgraph | |
| Oct 5, 2023 at 15:01 | comment | added | Naysh | Yes this question is about subgraphs (any subset of edges), definitely NOT induced subgraphs. | |
| Oct 5, 2023 at 14:59 | comment | added | JoshuaZ | Do you mean to ask about subgraphs here and not induced subgraphs? | |
| Oct 5, 2023 at 14:48 | history | asked | Naysh | CC BY-SA 4.0 |