Random graphs, random triangle-free graphs, and random partial orders

DOI10.1007/3-540-45506-X_8MaRDI QIDQ4542180zbMATH OpenFDO

Authors Hans Jürgen Prömel, Anusch Taraz

Publication date 4 August 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45506-X_8

zbMATH Keywords

chromatic number of random graphclique number of random graphevolution of random triangle-free graphsrandom partial orderstriangle-free graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorics of partially ordered sets (06A07)

Review text

A nice and accessible introduction to an aspect of random graph theory: given properties \(P\) and \(Q\), what is the probability that a random graph satisfying \(P\) also satisfies \(Q\)? The paper presents a selection of results on random triangle-free graphs, the clique and chromatic numbers of random graphs, and on random partial orders, most of them with proofs using the first and second moment methods. For the entire collection see [Zbl 0978.00022].

Recommendations

• scientific article; zbMATH DE number 1161245
• Random graphs: models and asymptotic characteristics
• scientific article; zbMATH DE number 18981
• On the chromatic number of random graphs
• scientific article; zbMATH DE number 863475

Cited in

(11)

• On retracts of the random graph and their natural order
• For which densities are random triangle-free graphs almost surely bipartite?
• Sandwiching random graphs: universality between random graph models
• Random cyclic triangle-free graphs of prime order
• On the triangle space of a random graph
• scientific article; zbMATH DE number 845673 (Why is no real title available?)
• scientific article; zbMATH DE number 850234 (Why is no real title available?)
• Linear orderings of random geometric graphs
• Non‐orderability of random triangular groups by using random 3CNF formulas
• On the evolution of structure in triangle-free graphs
• On the chromatic number of random triangle-free graphs

This page was built for publication: Random graphs, random triangle-free graphs, and random partial orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4542180)