Induced subgraphs with distinct sizes

DOI10.1002/RSA.20250MaRDI QIDQ3608312zbMATHOpenAlexFDO

Authors Noga Alon, Alexandr Kostochka

Publication date 4 March 2009

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20250

zbMATH Keywords

random graphinduced subgraphsRamsey graphssizes of subgraphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Generalized Ramsey theory (05C55)

Recommendations

• Induced subgraphs of given sizes
• Induced subgraphs of prescribed size
• Disjoint induced subgraphs of the same order and size
• Graphs with a small number of distinct induced subgraphs
• Induced subgraphs with many distinct degrees
• On the number of distinct induced subgraphs of a graph
• Graphs Having Small Number of Sizes on Induced k‐Subgraphs
• scientific article; zbMATH DE number 3898936
• Sizes of induced subgraphs of Ramsey graphs
• Sizes of graphs with induced subgraphs of large maximum degree

Cites work

• Cutting a graph into two dissimilar halves
• Graphs Having Small Number of Sizes on Induced k‐Subgraphs
• Induced subgraphs of Ramsey graphs with many distinct degrees

Cited in

(12)

• Graphs Having Small Number of Sizes on Induced k‐Subgraphs
• Disjoint induced subgraphs of the same order and size
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Anticoncentration for subgraph statistics
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Sizes of induced subgraphs of Ramsey graphs
• The parameterized complexity of \(k\)-edge induced subgraphs
• On the sizes of large subgraphs of the binomial random graph
• Ramsey graphs induce subgraphs of quadratically many sizes
• Graphs with a small number of distinct induced subgraphs
• The multiplication table problem for bipartite graphs

This page was built for publication: Induced subgraphs with distinct sizes

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