Choose largest R subset that any P elements has no intersection

Question

Given:

1. A set S of N integers
2. A set T contains some p-integer subsets of S, i.e. some subsets of size p

Goal: Find the largest subset H of the set S, where all p-integer subsets of H is not in T.

P/S: It is great to know the size r of H in advance.

For example:

Given:

S = {1,2,3,4,5}

p = 2, T = {{1,2},{1,4},{2,3}}

In context of sets, {1,2} are same to {2,1} and so on.

Then, we have:

H = {1,3,5} because all 2-integer subsets of H {1,3}, {1,5} and {3,5} are not in T

or H = {2,4,5} because {2,4}, {2,5} and {4,5} are not in T

or H = {3,4,5} because {3,4}, {3,5} and {4,5} are not in T

In 3 cases, sizes of H are 3; hence, r = 3.

Answer 1

You can solve the problem via integer linear programming as follows. For $i\in S$, let binary decision variable $x_i$ indicate whether $i\in H$. The problem is to maximize $\sum_i x_i$ subject to linear constraints $$\sum_{i\in t} x_i \le p-1$$ for all $t\in T$.