Ramsey numbers of partial order graphs (comparability graphs) and implications in ring theory

DOI10.1515/MATH-2020-0085MaRDI QIDQ2053552zbMATH OpenOpenAlexWikidataFDO

Authors Ayman Badawi, Roswitha Rissner

Publication date 29 November 2021

Published in Open Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Ramsey number, partial order, partial order graph, inclusion graph

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10) Partial orders, general (06A06) Ideals and multiplicative ideal theory in commutative rings (13A15)

Abstract: For a partially ordered set $(A,le)$, let $G_A$ be the simple, undirected graph with vertex set $A$ such that two vertices $aeqbinA$ are adjacent if either $aleb$ or $blea$. We call $G_A$ the emph{partial order graph} or emph{comparability graph} of $A$. Further, we say that a graph $G$ is a partial order graph if there exists a partially ordered set $A$ such that $G=G_A$. For a class $mathcalC$ of simple, undirected graphs and $n$, $mge1$, we define the Ramsey number $mathcal{R}_{mathcalC}(m,n)$ with respect to $mathcalC$ to be the minimal number of vertices $r$ such that every induced subgraph of an arbitrary partial order graph consisting of $r$ vertices contains either a complete $n$-clique $K_n$ or an independent set consisting of $m$ vertices. In this paper, we determine the Ramsey number with respect to some classes of partial order graphs. Furthermore, some implications of Ramsey numbers in ring theory are discussed.

Review text

The authors here determine the Ramsey number of partial order graphs. For a partially ordered set $(A,\leq)$, let $G_A$ be the simple, undirected graph with vertex set $A$ such that two vertices $a\neq b\in A$ are adjacent if either $a\leq b$ or $b\leq a$. They call $G_A$ the partial order graph (comparability graph) of $A$. Also, they call a graph $G$ a partial order graph if there exists a partially ordered set $A$ such that $G = G_A$. For a class of simple, undirected graphs and $n$, $m\geq 1$, they defined the Ramsey number $R_C(n, m)$ with respect to the class $C$ to be the minimal number $r$ of vertices such that every induced subgraph of an arbitrary graph of $r$ vertices contains either a complete $n$-clique $K_n$ or an independent set consisting of $m$ vertices. They show that the Ramsey number $R_{\mathrm{PoG}}(n,m)$ for the class $\mathrm{PoG}$ of partial order graphs equals $(n- m)(m-1)+1$. They also study subclasses of partial order graphs that appear in the context of ring theory. They establish that for the classes PDG of perfect divisor graphs, DivG of divisibility graphs, IDG of inclusion ideal graphs, MATG of matrix graphs, and IdemG of idempotent graphs of rings, the respective Ramsey numbers equal to $R_{\mathrm{PoG}}$. The authors also present a subclass of partial ordered graphs with respect to which the Ramsey numbers are non-symmetric.

Recommendations

• Ramsey numbers for partially-ordered sets
• Ramsey numbers of ordered graphs
• Zero-divisor graphs of partially ordered sets
• Ramsey partial orders from acyclic graphs
• scientific article; zbMATH DE number 3902698

Cites work

• A survey of bounds for classical Ramsey numbers
• Combinatorial Relations and Chromatic Graphs
• Graph classes and Ramsey numbers
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 6139955 (Why is no real title available?)
• On the Ramsey numbers R(3,8) and R(3,9)
• Partially ordered rings
• Some graph theoretic results associated with Ramsey's theorem
• The inclusion ideal graph of rings
• The value of the Ramsey numberr(3, 8)

Cited in

(3)

• Ramsey-type results for unions of comparability graphs
• Ramsey numbers for partially-ordered sets
• The n-total graph of a commutative ring

This page was built for publication: Ramsey numbers of partial order graphs (comparability graphs) and implications in ring theory

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