Ref.: Duchet. Convexity in Combinatorial Structures, 1985.
I am using the characterisation given in [Ref, p. 269] for the Caratheodory number: the Caratheodory number equals the least integer k such that every k+1-point set A satisfies: = U , for a in A. Where < > is the convex hull, U union of sets and \ set difference.
I have been trying various examples for the hypercube and so far all of them fulfil the property above for k = 2. For instance, consider the 4-dim hypercube. Let A = {0000, 1000, 1010}. Then we have:
1. = {0000, 1000, 1010, 0010}
2. = {1000, 1010}
3. = {0000, 1010, 1000, 0010}
4. = {0000, 1000}
Therefore, = U U . I haven't yet found an example of A where this does not happen.
I would appreciate if someone could provide a counterexample. Also I would appreciate reference to papers where they provide a Theorem/Corollary/Lemma for the Caratheodory num of the hypercube if any.
Thank you.
Your statement does not define precisely what is a convex set in the hypercube. The most usual convexity for the hypercube is relative to the Hamming distance :
- The distance d(x,y) of two vectors is the number of coordinates that differ in x and in y.
- A subset C of Qn is convex if, for any x,y in C, and for every z in Qn such that d(x,y)=d(x,z)+d(z,y), the element z belongs to C.
With this definition (which probably coincide with your's), the hypercube Qn has n as Caratheodory number : Consider the "unit vectors" u_i = (00...010...0) , with a single non zero coordinate in position i. The hypercube is the convex hull of the set A of all u_i's. But, for each i, the vector u=(111...1) is not in the convex hull of A\x_i. (Remark that the convex hull of A\u_i is the hypercube of dimension n-1 formed with vectors whose the i-th coordinate is 0).
This prove that the Caratheodory number is at least n.
To prove equality is very easy, using the definiton of the Hamming distance.
Thank you very much. Your answer was helpful.
Yes. I meant the geodesic interval convexity using the Hamming distance. It seems I didn't notice the example for the set of "unit vectors" you mentioned. Certainly, it has Carathéodory number n.
Kindest regards,
Marcos.
- Badges
- Science topic