Conjecture 16. For all k ě 6, k even, such that the dimension of the solution space of a1 x1 ` .
Statement
Conjecture 16. For all k ě 6, k even, such that the dimension of the solution space of a1 x1 . . . ak xk “ 0, b1 x1 . . . bk xk “ 0 is k ´ 2, and q sufficiently large, we have that the pair of equations is uncommon. Natasha Morrison Fix a pair of equations a1 x1 . . . ak xk “ 0 b1 x1 . . . bk xk “ 0. We say this pair of equations is common with respect to 2-coloring if for all n and f : Fnq Ñ r0, 1s that ˆź ź ˙ Ea1 x1 ...ak xk “0 f pxi q p1 ´ f pxi qq ě 21´k . b1 x1...`bk xk “0 i i Lutz Warnke In a landmark paper from 1987, Shamir and Spencer [5] proved that the chromatic number χpGn,p q of an n-vertex binomial ? random graph Gn,p is typically contained in an interval of length at most \omega n, where \omega “ \omegapnq is an arbitrary function with \omega Ñ 8 as nÑ 8, as usual. For constant edge-probabilities p P p0, 1q, Alon noticed ? in the 1990s that this concentration interval length can be slightly improved to \omega n{ log n, see [2, Excercise 7.9.3] and Scott’s note [4]. In the sparse case where p “ ppnq Ñ 0 vanishes as n Ñ 8., i.e., for edge-probabilities of form p “ n´\alpha with \alpha P p0, 1{2q, Shamir and Spencer proved in their 1987? paper that χpGn,p q is typically contained in an interval of length at?most \omega np log n, and a modern inspection of their proof reveals that length \omega np suffices. Very recently Surya and Warnke [6] extended Alon’s logarithmic improvement to the sparse case (by avoiding large deviation inequalities such as Janson’s inequality, instead relying on more robust Chernoff bound based arguments), obtaining the following result. Theorem 17 ([6]). Let \omega “ \omegapnq Ñ 8 as n Ñ 8 be an arbitrary function, and let \delta P p0, 1q be a constant. If the edge-probability p “}
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.