On Ramsey-minimal infinite graphs

DOI10.37236/10046MaRDI QIDQ2656900zbMATH OpenOpenAlexFDO

Authors Valentino Vito, Jordan Mitchell Barrett

Publication date 17 March 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3735863 (Why is no real title available?)
• scientific article; zbMATH DE number 3520447 (Why is no real title available?)
• scientific article; zbMATH DE number 2108139 (Why is no real title available?)
• Automorphisms and endomorphisms of infinite locally finite graphs
• Graph Ramsey theory and the polynomial hierarchy
• Graph theory
• Mutually embeddable graphs and the tree alternative conjecture
• On the metric dimension of infinite graphs
• On the minimum degree of minimal Ramsey graphs for multiple colours
• Self-embeddings of computable trees
• Self-embeddings of trees
• Strong Twins of Ordinary Star-Like Self-Contained Graphs

Cited in

(13)

• On Ramsey minimal graphs
• On Ramsey Minimal Graphs
• An accessibility theorem for infinite graph minors
• Ramsey-minimal graphs for forests
• scientific article; zbMATH DE number 3520447 (Why is no real title available?)
• Constructions of infinite graphs with Ramsey property
• Infinite Ramsey-minimal graphs for star forests
• On highly ramsey infinite graphs
• scientific article; zbMATH DE number 3970796 (Why is no real title available?)
• Minor-equivalence for infinite graphs
• On graphs with Ramsey-infinite blocks
• PROBLEMS AND RESULTS IN FINITE AND INFINITE COMBINATORIAL ANALYSIS
• scientific article; zbMATH DE number 3672341 (Why is no real title available?)

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)