On Ramsey-minimal infinite graphs

DOI10.37236/10046zbMATH Open1464.05261arXiv2011.14074OpenAlexW3107545586MaRDI QIDQ2656900FDOQ2656900

Authors: Valentino Vito, Jordan Mitchell Barrett 

Publication date: 17 March 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: For fixed finite graphs $G$, $H$, a common problem in Ramsey theory is to study graphs $F$ such that $Fo(G,H)$, i.e. every red-blue coloring of the edges of $F$ produces either a red $G$ or a blue $H$. We generalize this study to infinite graphs $G$, $H$; in particular, we want to determine if there is a minimal such $F$. This problem has strong connections to the study of self-embeddable graphs: infinite graphs which properly contain a copy of themselves. We prove some compactness results relating this problem to the finite case, then give some general conditions for a pair $(G,H)$ to have a Ramsey-minimal graph. We use these to prove, for example, that if $G=S_{i}nfty$ is an infinite star and $H=n{K}_2$, $nge1$ is a matching, then the pair $(S_{i}nfty,n{K}_2)$ admits no Ramsey-minimal graphs.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 3970796
• On graphs with Ramsey-infinite blocks
• scientific article; zbMATH DE number 3683630
• On Ramsey \((K_{1,2},P_4)\)-minimal graphs
• Ramsey-minimal graphs for star-forests

zbMATH Keywords

matchingcomb graphKoenig's Lemmaself-embeddable graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Infinite graphs (05C63) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• On the minimum degree of minimal Ramsey graphs for multiple colours
• Graph theory
• Graph Ramsey theory and the polynomial hierarchy
• Title not available (Why is that?)
• On the metric dimension of infinite graphs
• Automorphisms and endomorphisms of infinite locally finite graphs
• Mutually embeddable graphs and the tree alternative conjecture
• Self-embeddings of computable trees
• Self-embeddings of trees
• Title not available (Why is that?)
• Strong Twins of Ordinary Star-Like Self-Contained Graphs

Cited In (13)

• On Ramsey Minimal Graphs
• An accessibility theorem for infinite graph minors
• Title not available (Why is that?)
• Ramsey-minimal graphs for forests
• Constructions of infinite graphs with Ramsey property
• Infinite Ramsey-minimal graphs for star forests
• Title not available (Why is that?)
• On highly ramsey infinite graphs
• Minor-equivalence for infinite graphs
• On graphs with Ramsey-infinite blocks
• PROBLEMS AND RESULTS IN FINITE AND INFINITE COMBINATORIAL ANALYSIS
• Title not available (Why is that?)
• On Ramsey minimal graphs

This page was built for publication: On Ramsey-minimal infinite graphs

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