ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Open questions To conclude, by our results it follows that there is a constant c ⩽ 60 such that any n-vertex properly edge-coloured graph G with at least n(log n)c edges contains a rainbow subdivision of Km . We pose the following question. that no colour is used on too many of these paths P (v) and Q(v). It easily follows that for almost all pairs (u, v) with u, v \in U , the paths P (u) and Q(v) are colour- disjoint. This, combined with the fact that most pairs in U are good (in the sense mentioned earlier), implies that there exists at least one good pair (u, v) for which P (u) and Q(v) are colour-disjoint. This allows us to find a suitable short rainbow u, v-path L such that P (u) \cup L \cup Q(v) is a rainbow x, y-walk which contains the desired rainbow x, y-path. To prove Theorem 4 about r-blow-ups of subdivisions of cliques, we use similar arguments as the ones for proving Theorem 2, albeit tailored to the setup of r-blow- 1 60 ups. Recall that we are given a graph G on n vertices with at least n2− r (log n) r edges. A supersaturation result due to Erdős and Simonovits [3] implies that G has many copies of Kr,r . Our approach is to take a large collection F of copies of Kr,r in G and consider an auxiliary graph H whose vertices are r-sets of vertices in G, and whose edges correspond to copies of Kr,r in F. To find a blow-up of a Km -subdivision in G, it would suffice to find a ‘clean’ subdivision of Km in H, denoted K Question 6. Fix m ⩾ 2. What is the smallest c such that for all sufficiently large n the following holds: if G is a properly edge-coloured graph on n vertices with at least Ω(n(log n)c ) edges, then it contains a rainbow subdivision of Km ? In particular, is c = 1? 1 60 From our results it also follows that any n-vertex graph with at least n2− r (log n) r edges contains an r-blow-up of a subdivision of Km . This bound is tight up to 60 (log n) r factor, due to the following proposition, which was mentioned in [4] as a remark. We pose the following question, which strengthens Question 6.2 in [4].

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.