Egy társaságban 5 nő és 5 férfi van. Legfeljebb hány ismeretség van a társaság tagjai között, ha tudjuk, hogy a társaság azonos nemü tagjai nem ismerik egymást és nincs 2 olyan nő, akinek lenne 2 közös férfiismerőse?

Gondolom grafelmeletes megkozelites kell. Rajzold fel mint paros grafot a ferfiak es nok halmazat.

[link]

koztuk az ismeretsegeket az osszekoto vonalak jelolik.

Az hogy nincs ismeretseg az azonos nemuek kozott, pont azt jelenti, hogy paros graffal van dolgunk.

Milyen körök lehetnek benne? mivel páros a gráf, ezért csak páros hosszusaáguak lehetnek, de nem lehet 4 hosszu, mert nincs 2 olyan no akinek lenne 2 kozos ferfi ismerose, tehat a legrovidebb kor az 6 hosszusagu lehet.

A teljes P(5,5) paros grafban 5*5=25 el van, de itt nyilvan lesz egy csomo 4 hosszu kor. Egeszen pontosan 5*5*4*4/4= 100 db 4 hosszu kor lesz. 1 el elvetelevel a 4 hosszu korok szama 16-tal csokken. Egy ujab el elvetele ezutan 15 negy hoszu kort vesz el. ...

16+15+14+13+12+11+10+9 =100 db 4 hosszusagu kor megszunetesehez tehat 8 eletel kell venni, vagyis maximum 25-8 =17 el lehet a grafban.

Ez valoban letre is hozhato igy:

Nok: Z,X,C,V,B

Ferfiak: Q,W,E,R,T

Ismeretsegek:

Z-Q , B-T

Z-W , B-R

Z-E , B-E

X-Q , X-T

C-W , C-R

V-Q , V-R

Odáig én is eljutottam, hogy az első él elvételével 16-tal csökken az eredetileg 100 db. 4 hosszú kör száma (én azokat bow-tie (csokornyakkendő) köröknek hívtam magamban, mert olyan az alakjuk, ha a férfiakat és nőket két sorban helyezzük el.)

Viszont a következő él már nem 15-tel csökkenti a bowtie-ok szamát, csak 12-vel, aztán 8-cal, aztán ha teljesen máshonnan veszek el élet, akkor megint 12-vel, aztán 9-cel, majd 6-tal, stb. Nem igazán jöttem rá, hogy hogyan lehetne megfogni. (Az eleje még ok, 4·4, 4·3, 4·2, 3·4, 3·3, 3·2, stb., de aztán nem egyértelmű.)

Szóval a 25-8=17 megoldás szerintem nem jó, te is, BKRS, egy 12-es kiosztást adsz meg végül, mint lehetséges kiosztást, nem pedig 17-eset.

Más oldalról is próbalkoztam: Ha nem lenne benne egyetlen kör sem, vagyis fáról lene szó, akkor n-1 (9) éle lenne. Ehhez próbáltam hozzáadni éleket úgy, hogy 6 hosszú kört hozzanak csak létre, és max 3 élet tudtam csak hozzáadni. Tehát így is 12 jön ki megoldásnak, de nem tudom bizonyítani, hogy nem lehet több.

Az én 12-es kiosztásom egyebként ilyen, hasonlóképpen amerikai QWERTY billentyűzetet véve alapul, (bár inkább az ASDFG sort használom a nők számára a ZXCVB helyett, mert magyar billentyűzeten a Z helyén azt hiszem Y van)

Szóval egy lehetséges fa (tehát kör nélküli) kiindulás:

QA, AW, WS, SE, ED, DR, RF, FT, TG

ez tehát 9 hosszú. Ezt a 3 élet lehet még hozzáadni:

QG, AR, EG

így lesz 12 hosszú.

Ah, OK latom mar mit rontottam el.

Szoval nezzuk akkor megegyszer, mashogy.

XZCVB az egyik csoport es YQWERT a masik (van ugye az x-es meg az y-os csoport, kromoszoma szerint pl, mindegy))

Szoval akkor legyen egy maximalis fokszamu pont: Q.

|Q|=5 eseten |Y|=|W|=|E|=|R|=|T|=1 kell hogy legyen.

Ez osszesen 9 ismerettseg lehet.

|Q|=4

Ekkor ugyanezen az oldalon lehet mindenkinek 2 ismeretsege, senkinek nem lehet 3. Ez 12.

|Q|=2

Ekkor a max ismeretseg szam 2, vagyis az osszes ismeretseg max 10, tehat ez rosszabb mint a |Q=4| eset

|Q|=1 ekkor mindenki max 1 fot ismer hiszen Q fokszama max volt, ez meg rosszabb eset.

Marad meg a

|Q|=3 eset.

Q-n kivul a maradekbol a max foxamu lgyen W.

|W|=1 eseten az ossz fokszama a csoportnak 7

|W|=2 eseten az osszfokszama a csoportnak legfeljebb 11, meg mindig nem jobb mint a |Q|=4 eset.

|W|=3 3+3=6 es Q-nak es W-nek nincs 2 kozos ismerose, tehat pontosan 1 van.

Mondjuk Q ismerosei:

Z,X,C

W ismerosei C,V,B

Ha nem ez lenne akkor csak at kene az egeszet cimkezni, tehat az altalanossagot egyelore nem szoritottuk meg.

Tehat akkor eddig ez van:

Q-Z, W-B

Q-X, W-V

Q-C, W-C

Namost a kovetkezo legnagyobb fokszamu a Q csoportjaban (Q-t es W-t mar nem szamolva) legyen mondjuk E.

|E|=3 nem lehet.

|E|=1 eseten az ossz fokszam 3+3+3=9, aminel mar volt jobb, tehat az erdekes eset az amikor az osszes vissza levonek 2 a fokszama, amikor az osszfokszam 3+3+6=12.

Ilyet meg mar lattunk.

Mindenesetre ezzel annyit azert bizonyitottunk, hogy 12-nel nagyobb az egyik oldal total fokaszama nem lehet.

Kivancsi lennek van-e ennek valami otletes szamitasa n ferfi es m no eseten.

Hany ele van egy negyszo mentes paros grafnak?

Haromszog mentes grafokrol hallottam, a max elszamu (adott szamu pontr nezve) haromszogmentes grafok azok pontosan a paros grafok. Azthiszem ez vagy Turan tetele vagy annak egy kovetkezmenye.

[link]

Nyilvan akkor azok a grafok amikben a legkisebb kor 6 es nincsenek paratlan koreik, azok pont a grafok amik nekunk kellenek.

Ha valamit erre ki lehetne szamolni az erdekes lenne, csodalkoznek ha nem lenne valami valahol errol.

Tud valaki egy grafelmelet professzort?

Én is megkérdeztem egy matematikus ismerősömet. Azt mondta, az ilyeneknek ritkán van zárt képlet megoldása, legfeljebb alsó és felső becslése, vagy az aszimptotikus viselkedésére lehet valamit mondani.

Lovász véleménye engem is érdekel :)