ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 5.2] even predicted that for every fixed k \geq 3 we will have Pr (k) = Θ(r \cdot (fk,k+1 (r))2 ). Considering the recent improvements of Mubayi and Verstraete [9] on the Erdős- Rogers function, Theorem 2 comes within a log-factor of resolving this conjecture. Good constructions for the Erdős-Rogers function will be extremely useful for us as well, but creating color patterns using them requires additional ideas. The general approach to construct the desired color patterns is to start with an ”appropriate” u-uniform linear hypergraph on [n] with essentially as many 2 hyperedges as possible, that is, in the order nu2 . Then one assigns one of r colors to each hyperedge “appropriately”, to indicate which color pairs of vertices inside the hyperedge will receive should they be chosen to be an edge at all. Here the linearity of the hypergraph plays a crucial role: every pair of vertices belongs to (at most) one hyperedge. Finally, one constructs the graphs Gi by dropping an ”appropriately” random k-partite graph within each hyperedge of assigned color i, where the choices for different hyperedges are usually independent. This random choice must balance that no Kk+1 is created from the edges coming from within different hyperedges, yet there are enough edges so that any n/r-subset of the vertices contains a Kk . The crux of the matter is how to define the various occurrences of ”appropriate” above so that they complement each other well. In the construction of Fox et al. [6] for (2) (crucially making use of the Erdős- Rogers construction of Dudek, Retter, and Rödl [4]) and that of Hàn et al. [8] for (4) the linear hypergraph is essentially given by the lines of an (affine or projective) plane of order q and the ”appropriate” color assignment chosen randomly. In the constructions of Fox et al. [6] for (5) and of Bamberg et al. [1] for (6) the linear hypergraph is given by some (pseudo)lines in a higher dimensional space and the color-assignment is defined algebraically. The point of these assignments is to ensure that the hypergraph of each color class is triangle-free, hence the Kk+1 - freeness of each Gi will be automatic once the graphs inside the hyperedges are Kk+1 -free. In our construction we also start with the projective plane, working in the dual setup, so the lines will correspond to vertices and the vertices correspond to the hyperedges. We choose the order to be q 2 , so we are able to make use of Hermitian unitals and its beneficial algebraic and combinatorial properties. One of the main ideas of our construction is to combine the probabilistic color assignment to the hyperedges with an appropriate algebraic one. Unlike in [6] and [1], our algebraic color assignment will not guarantee immediate Kk+1 -freeness, but will however ensure that the analysis of Kk+1 -freeness will only have to consider very limited The report passage is retained verbatim as the relevant context for this extracted problem.

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.