On efficient constructions of short lists containing mostly Ramsey graphs

DOI10.1007/978-3-642-38236-9_19MaRDI QIDQ4922127zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 28 May 2013

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

Full work available at URL https://arxiv.org/abs/1210.4408

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: One of the earliest and best-known application of the probabilistic method is the proof of existence of a 2 log n$-Ramsey graph, i.e., a graph with n nodes that contains no clique or independent set of size 2 log n. The explicit construction of such a graph is a major open problem. We show that a reasonable hardness assumption implies that in polynomial time one can construct a list containing polylog(n) graphs such that most of them are 2 log n-Ramsey.

Recommendations

• scientific article; zbMATH DE number 2196516
• Large cliques and independent sets all over the place
• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs

Cited in

(3)

• Constructing Ramsey graphs from Boolean function representations
• Constructive lower bounds for off-diagonal Ramsey numbers
• A short constructive proof of the Erdős-Gallai characterization of graphic lists

This page was built for publication: On efficient constructions of short lists containing mostly Ramsey graphs

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