Skip to main content
corrected product assertion; deleted 6 characters in body; added 16 characters in body
Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Like algebraic structures, intersecting set systems lend themselves to nice constructions, such as (isomorphic image of a) Cartesian product, proper subsystem, and homomorphic image. Unfortunately, I do not know that these are enough to generate all Intersecting set systems, even given a somewhat rich collection of building blocks.

For c-uniform systems, the product construction seems to be multiplicative on the measure f(c); for subsystems it does not decrease the measure. The situation is not so clear for homomorphic image; it may be possible to decrease the measure, but it is tricky to come up with a map that makes the homomorphic image d-uniform for some d. I suspect that such maps will turn out not to decrease f(c)

Note also that if there is a c-uniformEDIT For intersecting set systemsystems with f(c) <smallest size of set c being finite, the rank function mentioned in the post clearly has minimum (1- epsilon)/c$1/c$, so the epsilon can be magnified by taking a cartesian power. Thisproduct construction is a reason (but not a proof)as useful for me to suspect that theestablishing a lower bound across all c-uniform set systemsas it is for fproviding (c) is 1/c.

Other natural constructions I have looked at seemsay for those composite $c$ not corresponding to affectan order of a rank function similar to f(cprojective plane). If one can turn the more examples of low rate c-uniform intersecting set system into an algebraic structure, then I think f(c) will be shown to have 1/c as a lower boundsystems.

  Note also that if there is a c-uniform set system with f(c) < (1- epsilon)/c, the epsilon can be magnified by taking a cartesian power. This is a reason (but not a proof) for me to suspect that the lower bound across all c-uniform set systems for f(c) is 1/c.

Other natural constructions I have looked at seem not to affect a rank function similar to f(c). If one can turn the intersecting set system into an algebraic structure, then I think f(c) will be shown to have 1/c as a lower bound. END EDIT

One idea that I will let others play with. For an intersecting set system on a universe U, pick a in U and then gather all sets which have a as a member. From the remaining sets which do not contain a, pick an element b, and gather all remaining sets which have b as a member. Continue picking such elements to weed out the sets in the system. The set chosen {a,b,c,...} is either a set in the Interesectingintersecting set system, or can be added as one. If the set system is c-uniform and nontrivial (so that there is no element a beloning to all the sets, I think it a nice conjecture that this set is of size at most c, and can be helpful in showing f(c) <= 1/c, and can be helpful in showing f(c) <= 1/c.

Gerhard "Missed It By That Much" Paseman, 2011.05.20

Like algebraic structures, intersecting set systems lend themselves to nice constructions, such as (isomorphic image of a) Cartesian product, proper subsystem, and homomorphic image. Unfortunately, I do not know that these are enough to generate all Intersecting set systems, even given a somewhat rich collection of building blocks.

For c-uniform systems, the product construction seems to be multiplicative on the measure f(c); for subsystems it does not decrease the measure. The situation is not so clear for homomorphic image; it may be possible to decrease the measure, but it is tricky to come up with a map that makes the homomorphic image d-uniform for some d. I suspect that such maps will turn out not to decrease f(c)

Note also that if there is a c-uniform set system with f(c) < (1- epsilon)/c, the epsilon can be magnified by taking a cartesian power. This is a reason (but not a proof) for me to suspect that the lower bound across all c-uniform set systems for f(c) is 1/c.

Other natural constructions I have looked at seem not to affect a rank function similar to f(c). If one can turn the intersecting set system into an algebraic structure, then I think f(c) will be shown to have 1/c as a lower bound.

 

One idea that I will let others play with. For an intersecting set system on a universe U, pick a in U and then gather all sets which have a as a member. From the remaining sets which do not contain a, pick an element b, and gather all remaining sets which have b as a member. Continue picking such elements to weed out the sets in the system. The set chosen {a,b,c,...} is either a set in the Interesecting set system, or can be added as one. If the set system is c-uniform and nontrivial (so that there is no element a beloning to all the sets, I think it a nice conjecture that this set is of size at most c, and can be helpful in showing f(c) <= 1/c.

Gerhard "Missed It By That Much" Paseman, 2011.05.20

Like algebraic structures, intersecting set systems lend themselves to nice constructions, such as (isomorphic image of a) Cartesian product, proper subsystem, and homomorphic image. Unfortunately, I do not know that these are enough to generate all Intersecting set systems, even given a somewhat rich collection of building blocks.

For c-uniform systems, the product construction seems to be multiplicative on the measure f(c); for subsystems it does not decrease the measure. The situation is not so clear for homomorphic image; it may be possible to decrease the measure, but it is tricky to come up with a map that makes the homomorphic image d-uniform for some d. I suspect that such maps will turn out not to decrease f(c)

EDIT For intersecting set systems with smallest size of set c being finite, the rank function mentioned in the post clearly has minimum $1/c$, so the product construction is not as useful for establishing a lower bound as it is for providing (say for those composite $c$ not corresponding to an order of a projective plane) more examples of low rate c-uniform intersecting set systems. Note also that if there is a c-uniform set system with f(c) < (1- epsilon)/c, the epsilon can be magnified by taking a cartesian power. This is a reason (but not a proof) for me to suspect that the lower bound across all c-uniform set systems for f(c) is 1/c.

Other natural constructions I have looked at seem not to affect a rank function similar to f(c). If one can turn the intersecting set system into an algebraic structure, then I think f(c) will be shown to have 1/c as a lower bound. END EDIT

One idea that I will let others play with. For an intersecting set system on a universe U, pick a in U and then gather all sets which have a as a member. From the remaining sets which do not contain a, pick an element b, and gather all remaining sets which have b as a member. Continue picking such elements to weed out the sets in the system. The set chosen {a,b,c,...} is either a set in the intersecting set system, or can be added as one. If the set system is c-uniform and nontrivial (so that there is no element a beloning to all the sets, I think it a nice conjecture that this set is of size at most c, and can be helpful in showing f(c) <= 1/c.

Gerhard "Missed It By That Much" Paseman, 2011.05.20

Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Like algebraic structures, intersecting set systems lend themselves to nice constructions, such as (isomorphic image of a) Cartesian product, proper subsystem, and homomorphic image. Unfortunately, I do not know that these are enough to generate all Intersecting set systems, even given a somewhat rich collection of building blocks.

For c-uniform systems, the product construction seems to be multiplicative on the measure f(c); for subsystems it does not decrease the measure. The situation is not so clear for homomorphic image; it may be possible to decrease the measure, but it is tricky to come up with a map that makes the homomorphic image d-uniform for some d. I suspect that such maps will turn out not to decrease f(c)

Note also that if there is a c-uniform set system with f(c) < (1- epsilon)/c, the epsilon can be magnified by taking a cartesian power. This is a reason (but not a proof) for me to suspect that the lower bound across all c-uniform set systems for f(c) is 1/c.

Other natural constructions I have looked at seem not to affect a rank function similar to f(c). If one can turn the intersecting set system into an algebraic structure, then I think f(c) will be shown to have 1/c as a lower bound.

One idea that I will let others play with. For an intersecting set system on a universe U, pick a in U and then gather all sets which have a as a member. From the remaining sets which do not contain a, pick an element b, and gather all remaining sets which have b as a member. Continue picking such elements to weed out the sets in the system. The set chosen {a,b,c,...} is either a set in the Interesecting set system, or can be added as one. If the set system is c-uniform and nontrivial (so that there is no element a beloning to all the sets, I think it a nice conjecture that this set is of size at most c, and can be helpful in showing f(c) <= 1/c.

Gerhard "Missed It By That Much" Paseman, 2011.05.20