4
$\begingroup$

Fix a positive integer $r$ and real $\delta \in (0,1)$.

Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., $G$ does not have any "large regular subgraph"). What can we say about $G$?

Question: What properties must such a graph $G$ have?

For example, must $G$ be sparse (can we get good upper bounds on the total number of edges in $G$)? Are there interesting structural properties $G$ must have? I would be interested in hearing about results in this vein even for some concrete small values of $r$, and fixed choices of $\delta$.

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you mean to ask about subgraphs here and not induced subgraphs? $\endgroup$
    – JoshuaZ
    Commented Oct 5, 2023 at 14:59
  • $\begingroup$ Yes this question is about subgraphs (any subset of edges), definitely NOT induced subgraphs. $\endgroup$
    – Naysh
    Commented Oct 5, 2023 at 15:01
  • 2
    $\begingroup$ 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 $\endgroup$
    – dbal
    Commented Oct 5, 2023 at 18:58
  • $\begingroup$ 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. $\endgroup$
    – Naysh
    Commented Oct 6, 2023 at 14:50
  • $\begingroup$ FYI, the results above are not about spanning subgraphs $\endgroup$
    – dbal
    Commented Oct 6, 2023 at 14:57

0

Reset to default

You must log in to answer this question.