Lower bounds on the chromatic number of random graphs (Q2678448): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q4705349 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Almost all graphs with average degree 4 are 3-colorable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques / rank
 
Normal rank
Property / cites work
 
Property / cites work: The two possible values of the chromatic number of a random graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: The concentration of the chromatic number of random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The condensation phase transition in random graph coloring / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The chromatic number of random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Upper-bounding the \(k\)-colorability threshold by counting covers / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the chromatic number of random regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The rank of sparse random matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Information-theoretic thresholds from the cavity method / rank
 
Normal rank
Property / cites work
 
Property / cites work: The asymptotic \(k\)-SAT threshold / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the chromatic number of random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Spin systems on Bethe lattices / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Chromatic Number of Random Graphs for Most Average Degrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the chromatic number of a random 5-regular graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Satisfiability threshold for random regular \textsc{nae-sat} / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum independent sets on random regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proof of the Satisfiability Conjecture for Large k / rank
 
Normal rank
Property / cites work
 
Property / cites work: The 3-XORSAT threshold. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3286850 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Replica bounds for optimization problems and diluted spin systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the independence and chromatic numbers of random regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4519896 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Broken replica symmetry bounds in the mean field spin glass model / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the chromatic number of random \(d\)-regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Random regular graphs of high degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Replica bounds by combinatorial interpolation for diluted spin systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: The chromatic number of random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Expose-and-merge exploration and the chromatic number of a random graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3359787 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Information, Physics, and Computation / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Sherrington-Kirkpatrick Model / rank
 
Normal rank
Property / cites work
 
Property / cites work: Spin glass models from the point of view of spin distributions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds for diluted mean-fields spin glass models / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Colouring Random 4-Regular Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Colouring Random Regular Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4413910 / rank
 
Normal rank

Revision as of 08:29, 31 July 2024

scientific article
Language Label Description Also known as
English
Lower bounds on the chromatic number of random graphs
scientific article

    Statements

    Lower bounds on the chromatic number of random graphs (English)
    0 references
    0 references
    0 references
    0 references
    23 January 2023
    0 references
    A formula for lower bounds on the chromatic number \(\chi(G)\) of a random graph \(G\) is established using the so-called interpolation method from mathematical physics, see \textit{F. Guerra} and \textit{F. L. Toninelli} [Commun. Math. Phys. 230, No. 1, 71--79 (2002; Zbl 1004.82004)], instead of the second moment method. For random \(d\)-regular graphs, \(G(n,d)\), the formula is expressed algebraically, while for binomial random graphs (Erdős-Rényi) a variational formula is obtained. The formulas are then used to calculate explicit (and improved) lower bounds on \(\chi(G (n,d))\) with small \(d\) as well as binomial random graphs of small average degree. For large (average) degree it is shown how the new formulas can be used to easily re-derive asymptotic formulas without lengthy and complicated combinatorial arguments.
    0 references
    chromatic number
    0 references
    random graph
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers