Algebraična kombinatorika - 16. mar. 2007

Povzetek predavanja:

• povezani grafi z natanko tremi lastnimi vrednostmi so krepko regularni,
• večkratnosti lastnih vredsnosti, in klasifikacija
  • tip I - konferenčni grafi in
  • tip II - celoštevilčne lastne vrednosti,
• Paleyjevi grafi,
• Kreinov pogoj in Smitovi grafi,
• grafi (negativnega) LS tipa (LS=latinski kvadrat),
• TD grafi in Steinerjevi grafi;
• enoličnost v primeru nekaterih parametrov
  • graf povezav polnega grafa K_n za n<>8, tj. takoimenovani trikotniški graf in
  • polnega dvodelnega grafa K_n,n za n<>4, takoimenovani mrežni grafi
  ter super-eksponentno mnogo grafov v primeru drugih parametrov
• grafi Latinski kvadratov, ki niso mrežni grafi in
• grafi Steinerjevih trojk, ki niso trikotni grafi;
• Neumaierjev izrek: krepko regularni grafi z najmanjšo lastno vrednostjo m, kjer je m naravno število, so s končno izjemami bodisi polni večdelni, Steinerjevi grafi ali bločni grafi transverzalnih designov.

in prosojnice:

• ac05_srg

Vse postscript pdf datoteke si lahko ogladate z Adobe Reader, ki so na voljo za večino računalnikov in brskalnikov.

Dodatna gradiva:

• wiki o krepko regularnih grafih
• Mathworld Wolfram o krepko regularnih grafih
• Gordon Royle vzdržuje listo krepko-regularnih grafov do 1000 vozlišč (vendar pa je Brouwerjeve lista zaenkrat nekoliko bolj popolna).
• najdite kakšno zanimivo tudi sami in mi jo pošljite.

Domače naloge (do 12. mar. 2007):

• 5. domača naloga