Induced Subgraphs With Many Distinct Degrees

DOI10.1017/S0963548317000256zbMath1378.05127arXiv1609.01677OpenAlexW2964343298MaRDI QIDQ4601057

István Tomon, Bhargav P. Narayanan

Publication date: 19 January 2018

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Erdős problemRamsey graphsdistinct degrees

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

A bipartite version of the Erdős–McKay conjecture ⋮ Distinct degrees and homogeneous sets ⋮ Distinct degrees in induced subgraphs ⋮ Proof of a conjecture on induced subgraphs of Ramsey graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced subgraphs of Ramsey graphs with many distinct degrees
• Erdős and Rényi conjecture
• Non-Ramsey graphs are \(c\log n\)-universal
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Low rank co-diagonal matrices and Ramsey graphs
• On a Ramsey type theorem
• Two-source dispersers for polylogarithmic entropy and improved ramsey graphs
• Explicit two-source extractors and resilient functions
• Some remarks on the theory of graphs

This page was built for publication: Induced Subgraphs With Many Distinct Degrees