Tight bounds on the Carathéodory and exchange numbers in △-convexity
Abstract
The △-convexity space on a finite, simple graph G = (V,E) is the collection 𝒞 of subsets S ⊆ V(G) such that whenever x ∈ V(G) forms a triangle with two vertices in S, we have x ∈ S. The members of 𝒞 are called convex sets, and the convex hull of a set S ⊆ V(G), denoted Hull(S), is the smallest member of 𝒞 that contains S. The Carathéodory (resp., exchange) number, c△(G) (resp., e△(G)), is the size of a largest Carathéodory (resp., exchange) independent subset of V(G). It was shown by Anand et al. (JCMCC 126, 2025, 11--27) that c△(G) ≤ t(G)+1 and e△(G) ≤ t(G) + 2, where t(G) is the number of triangles in G, and that these bounds are tight. They also computed c△(G) and e△(G) for a block graph G in terms of the number and arrangement of non-K2 blocks in G. In this paper, we point out a gap in the proof in Anand et al. of the first inequality, c△(G) ≤ t(G)+1, which has consequences for the proof of the second inequality, e△(G) ≤ t(G) + 2, as well. Moreover, the tightness results are inadvertently applied as characterizations of the extremal graphs, leading to incorrect computations of the Carathéodory and exchange numbers of block graphs in certain cases. We fix these gaps by giving a full proof of the first inequality via a different route from that in Anand et al. Together with the argument in Anand et al., this also completes the proof of the second inequality. Our proof also leads to a characterization of the extremal graphs for each bound, which we use to compute the Carathéodory and exchange numbers of block graphs and to identify the extremal block graphs. We also determine e△(G) exactly for k-trees for every k ≥ 2.
Related
- Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
- Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- Tight degeneracy bounds in online Ramsey games
BibTeX
@misc{kumar2026tight,
title = {{Tight bounds on the Carathéodory and exchange numbers in $\triangle$-convexity}},
author = {Vishnu Kumar and Brahadeesh Sankarnarayanan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34441},
eprint = {2609.34441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34441},
}
RIS
TY - UNPB
TI - Tight bounds on the Carathéodory and exchange numbers in △-convexity
AU - Vishnu Kumar
AU - Brahadeesh Sankarnarayanan
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34441
UR - https://arxiv.org/abs/2609.34441
AB - The △-convexity space on a finite, simple graph G = (V,E) is the collection 𝒞 of subsets S ⊆ V(G) such that whenever x ∈ V(G) forms a triangle with two vertices in S, we have x ∈ S. The members of 𝒞 are called convex sets, and the convex hull of a set S ⊆ V(G), denoted Hull(S), is the smallest member of 𝒞 that contains S. The Carathéodory (resp., exchange) number, c_△(G) (resp., e_△(G)), is the size of a largest Carathéodory (resp., exchange) independent subset of V(G). It was shown by Anand et al. (JCMCC 126, 2025, 11--27) that c_△(G) ≤ t(G)+1 and e_△(G) ≤ t(G) + 2, where t(G) is the number of triangles in G, and that these bounds are tight. They also computed c_△(G) and e_△(G) for a block graph G in terms of the number and arrangement of non-K_2 blocks in G. In this paper, we point out a gap in the proof in Anand et al. of the first inequality, c_△(G) ≤ t(G)+1, which has consequences for the proof of the second inequality, e_△(G) ≤ t(G) + 2, as well. Moreover, the tightness results are inadvertently applied as characterizations of the extremal graphs, leading to incorrect computations of the Carathéodory and exchange numbers of block graphs in certain cases. We fix these gaps by giving a full proof of the first inequality via a different route from that in Anand et al. Together with the argument in Anand et al., this also completes the proof of the second inequality. Our proof also leads to a characterization of the extremal graphs for each bound, which we use to compute the Carathéodory and exchange numbers of block graphs and to identify the extremal block graphs. We also determine e_△(G) exactly for k-trees for every k ≥ 2.
ER -