Ramsey graphs contain many distinct induced subgraphs

DOI10.1007/BF01789457zbMATH Open0728.05044MaRDI QIDQ804596FDOQ804596

Authors Noga Alon, Andras Hajnal 

Publication date 1991

Published in Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

Ramsey graphsmaximum number of vertices in a trivial induced subgraphnumber of isomorphism types of induced subgraphs

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55)

Recommendations

• Sizes of induced subgraphs of Ramsey graphs
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Ramsey graphs induce subgraphs of quadratically many sizes
• Graphs with a small number of distinct induced subgraphs
• Induced subgraphs of Ramsey graphs with many distinct degrees

Cites Work

• Graphs with a small number of distinct induced subgraphs
• On the number of distinct induced subgraphs of a graph
• Quantum private communication
• Ramsey graphs cannot be defined by real polynomials
• Ramsey-type theorems
• Some remarks on the theory of graphs

Cited In (15)

• Title not available (Why is no real title available?)
• On the number of induced subgraphs of a random graph
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Almost every \(n\)-vertex graph is determined by its \(3 \log_2n\)-vertex subgraphs
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Title not available (Why is no real title available?)
• Induced subgraphs of Ramsey graphs with many distinct degrees
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Erdős and Rényi conjecture
• Graphs with a small number of distinct induced subgraphs
• SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
• On the number of distinct induced subgraphs of a graph
• Distinct degrees in induced subgraphs
• Isomorphisms between random graphs
• Ramsey graphs induce subgraphs of many different sizes

This page was built for publication: Ramsey graphs contain many distinct induced subgraphs

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