Induced/Incomparable versus Ramsey
Yair Caro, Zsolt Tuza, Christina Zarb · 2026
Read Induced/Incomparable versus Ramsey by Yair Caro, Zsolt Tuza, Christina Zarb (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22077.txt.
Introduction
Yair Caro, Zsolt Tuza, and Christina Zarb study induced and incomparable graphs versus Ramsey-type problems. Two graphs on k vertices are incomparable when neither contains the other. A graph G is H-exact when every induced k-vertex subgraph is either H itself or incomparable with H. The paper studies the Exact(H) family and its bound f. For trees: for a tree on at least 3 vertices, f(T) lies between (k-1) times the ceiling of k over 2 minus 1 and (k-1) squared. Formulas cover stars, paths, and matchings.
Catalog record
| CREATOR | Yair Caro, Zsolt Tuza, Christina Zarb |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52929 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22077
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Induced/Incomparable versus Ramsey Yair Caro, Zsolt Tuza, Christina Zarb Abstract We consider the following problem: Let H H and F F be two graphs on k k vertices and assume F ≠ H F\neq H . We say that H H and F F are incomparable if neither F F nor H H contains the other. Let H H be a graph on k k vertices and let G G be a graph on at least k k vertices. Then G G is said to be H H -exact if any induced subgraph of G G on k k vertices is either isomorphic to H H or incomparable with H H . Exact( H H ) is the family of all graphs G G which are H H -exact. We pose the following problem: For a graph H H on k k vertices, determine or estimate f ( H ) = max { n : ∃ G ∈ Exact ( H ) , | V ( G ) | = n } f(H)=\max\{n:\exists G\in\text{Exact}(H),|V(G)|=n\} . Among the many results obtained in this paper the following are representatives concerning trees and matchings. 1. For a tree on k ≥ 3 k\geq 3 vertices, ( k − 1 ) ( ⌈ k 2 ⌉ − 1 ) ≤ f ( T ) ≤ ( k − 1 ) 2 (k-1)(\left\lceil\frac{k}{2}\right\rceil-1)\leq f(T)\leq(k-1)^{2} . 2. For k ≥ 4 k\geq 4 , f ( K 1 , k − 1 ) = ( k − 1 ) ( k − 2 ) f(K_{1,k-1})=(k-1)(k-2) . 3. For k ≥ 5 k\geq 5 , f ( P k ) = ( k − 1 ) 2 2 f(P_{k})=\frac{(k-1)^{2}}{2} if k k is odd and f ( P k ) = ( k − 1 ) ( k − 2 ) 2 + 1 f(P_{k})=\frac{(k-1)(k-2)}{2}+1 if k k is even. 4. f ( n K 2 ) = 3 n f(nK_{2})=3n for n = 2 , 3 n=2,3 and f ( n K 2 ) = 4 n − 4 f(nK_{2})=4n-4 for n ≥ 4 n\geq 4 . 0 0 footnotetext: 2020 Mathematics Subject Classification. 05C55. 1 Introduction An alternative formulation for the Ramsey numbers R(H,K_{k}) is that every graph G on at least R(H,K_{k}) vertices either contains H or has independence number \alpha(G)\geq k , that is it contains an induced E_{k}=\overline{K_{k}} . However, it is no longer true that R(H,F) , where F\notin\{K_{k},E_{k}\} , forces that every graph G on at least R(H,F) vertices contains either H or \overline{F} , as evident by red G=E_{n} versus blue \overline{G}=K_{n} for every n . We put forward two problems concerning this situation, which we shall present after introducing some necessary terminology. Let A and B be two graphs. By standard definition A is a subgraph of B if V(A)\subseteq V(B) and E(A)\subseteq E(B) . Moreover, if two vertices in A are adjacent whenever they are adjacent in B , then A is said to be an induced subgraph of B . If A is isomorphic to a subgraph (not necessarity induced) of B , then B is said to contain A . Let H be a graph on k vertices, and let G be a graph on at least k vertices. Then G is said to be H -exact if any induced subgraph of G on k vertices is either isomorphic to H or it neither contains nor is contained in H . Then, Exact (H) is the family of all graphs G which are H -exact. We say that a graph on k vertices is incomparable with H if it neither contains nor is contained in H . The set of all such graphs is denoted by Inc (H) . Then we let Leg (H) be H\cup\mbox{Inc}(H) . Therefore G is H -exact if all its induced subgraphs on k vertices are in Leg (H) . On the other hand if a graph on k vertices contains or is contained in H , we say it is comparable to H and the set of graphs comparable to H (including H ) is denoted by Com( H ). We let Com {}^{*}(H)=\text{Com}(H)\backslash\{H\} . We now present the two main definitions: For a graph H on k vertices, let 1. f(H)=\max\{n:\exists G\in\text{Exact}(H),|V(G)|=n\} . 2. g(H)= \min\{n:\forall G,|V(G)|\geq n,G\text{ contains a }k\text{-vertex induced graph }F\in\text{Com}(H)\}. Our main concern in this paper is either to determine the exact value of f(H) and g(H) , or to find lower and upper bounds for them. In Section 2 we present some simple constructions of H -exact graphs, which further motivate the study of f(H) , as well as some simple facts concerning the notation. In Section 3 we consider first problem 2 concerning the function g(H) and prove Theorem 3.1 that g(H)=R(H,\overline{H})=R(\overline{H},H)=g(\overline{H}) and use this result in Theorem 3.3 to get the lower bound f(H)=f(\overline{H})\geq R(H,\overline{H})-1 . This result has the immediate consequence that every graph G on at least R(H,\overline{H}) vertices contains a k -vertex induced subgraph F comparable with H , and a k -vertex induced subgraph Q comparable with \overline{H} , which supplies a strong answer to the phenomenon mentioned in the start of the introduction. A consequence of this lower bound is that f(H) can grow exponentially with |V(H)| , despite the difficulty to supply constructive examples of more than quadratic growth. We then consider H=K_{k}\setminus Q , and in particular prove that there exist 0<c_{0}<c_{1} such that \frac{c_{0}k^{2}}{\log k}\leq f(K_{k}\setminus K_{3})\leq\frac{c_{1}k^{2}}{\log k} . In Section 4 we determine the exact value of f(H) in terms of the Ramsey number involved for two families of graphs. For a given graph H on k vertices ( H\notin\{K_{k},E_{k}\} ), let U(H)=\{G:|V(G)|=k,\,e(G)=e(H)+1,\,G\mbox{ contains }H\} and let U(\overline{H})=\{G:|V(G)|=k,\,e(G)=e(\overline{H})+1,6,\,G\mbox{ contains }\overline{H}\} We prove Theorem 4.2: For H a graph on k vertices, H\notin\{K_{k},E_{k}\} , f(H)=R(U(H),U(\overline{H}))-1\leq R(K_{k},K_{k})-1 . Otherwise, f(H)=\infty . However, in practice it is not easy to extract lower and upper bounds from this Ramsey type expression, and we give more specific bounds when the structure of H is restricted. In Section 5 we consider lower bounds for f(H) in terms of graph parameters (mainly the independence number and the matching number), in the spirit of classical lower bounds in Ramsey theory. In Theorem 5.1, we prove, among other results, that if H is connected on k vertices with independence number \alpha(H) , then f(H)\geq(\alpha(H)-1)(k-1) and in Theorem 5.3, we prove that if H is a connected triangle-free graph on k vertices and matching number \mu(H) , then f(H)\geq(k-\mu(H)-1)(k-1) . Section 6 is devoted to trees and matchings. Here we prove the results mentioned in the abstract: 1. For a tree T on k\geq 3 vertices, (k-1)(\left\lceil\frac{k}{2}\right\rceil-1)\leq f(T)\leq(k-1)^{2} . 2. For k\geq 4 , f(K_{1,k-1})=(k-1)(k-2) . 3. For k\geq 5 , f(P_{k})=\frac{(k-1)^{2}}{2} if k is odd and f(P_{k})=\frac{(k-1)(k-2)}{2}+1 if k is even. 4. f(nK_{2})=3n for n=2,3 and f(nK_{2})=4n-4 for n\geq 4 . Section 7 contains open problems concerning f(H) . 2 Basic Observations and Simple Examples We first give some simple examples to illustrate the concept of H -exact. Construction via vertex transitive graphs : Let F be a