Induced subgraphs with distinct sizes

DOI10.1002/RSA.20250MaRDI QIDQ3608312zbMATH OpenOpenAlexFDO

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

induced subgraphsRamsey graphsrandom graphsizes of subgraphs

Mathematics Subject Classification ID

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

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

(14)

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

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)