New Bounds on Perfect Hash Families

I was able to improve a perfect hash family bound, in that PHFN(9, 4, 3) = 3 , whereas the previous known bound (I believe) was PHFN(9, 4, 3) \le 4.

The output of my program that generated it:

a(1,1,1) a(1,2,3) a(1,3,2) a(1,4,4) a(1,5,2) a(1,6,1) a(1,7,4) a(1,8,3) a(1,9,3) a(2,2,3) a(2,1,4) a(2,3,1) a(2,4,1) a(2,5,2) a(2,6,1) a(2,7,3) a(2,8,4) a(2,9,2) a(3,1,1) a(3,2,4) a(3,3,4) a(3,4,3) a(3,5,1) a(3,6,2) a(3,7,1) a(3,8,3) a(3,9,2)

where a(R,C,V) means at row R, column C, is value V.

I’m working on this as a class project – hopefully I can get better bounds for CPHFs as well!

Advertisements

One thought on “New Bounds on Perfect Hash Families

  1. Pingback: Perfect Hash Family Tables – Ryan Dougherty's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s