Timeline for Maximum number of four cycles with no intersecting three vertex paths

6 events

when toggle format	what		by	license	comment
Jun 11, 2020 at 13:56	history	edited	Adam P. Goucher	CC BY-SA 4.0	added 177 characters in body
Jun 11, 2020 at 13:50	comment	added	Balagopal Komarath		For the corrected question, a similar argument used for your lower bound works to obtain an $\Omega(n^3)$ bound.
Jun 11, 2020 at 13:10	comment	added	Balagopal Komarath		Yes. I was only asking for a large collection with no common $P_3$. I can see how my question is confusing. I will edit it.
Jun 11, 2020 at 12:36	comment	added	Adam P. Goucher		But your graph still has two 4-cycles -- such as $1,x,2,y,1$ and $3,x,2,y,1$ -- which share a common 3-vertex path ($x,2,y$). If you didn't mean that (and you're only interested in finding a large collection of 4-cycles on a common vertex set which pairwise share no common 3-vertex path), then your mention of 'an $n$-vertex simple undirected graph' is a red herring.
Jun 11, 2020 at 8:13	comment	added	Balagopal Komarath		A union of two $C_4$ without a common $P_3$ can have a $K_{2,3}$. For example, consider the $K_{2,4}$ where one partition has vertices $\{x, y\}$ and the other partition has $\{1,2,3,4\}$. This graph is the union of two cycles $1,x,2,y,1$ and $3,x,4,y,3$. These cycles do not have a common $P_3$.
Jun 7, 2020 at 20:34	history	answered	Adam P. Goucher	CC BY-SA 4.0