On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs
From MaRDI portal
Publication:4922127
DOI10.1007/978-3-642-38236-9_19zbMATH Open1382.05046arXiv1210.4408OpenAlexW1516130263MaRDI QIDQ4922127
Publication date: 28 May 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1210.4408
Analysis of algorithms and problem complexity (68Q25) Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
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)
