Diszkrét Matematika Workshop

Lunch break: 12:15 - 14:00

 

 

14:00-14:30	Bujtás Csilla: Gráfparaméterek becslése súlyok alkalmazásával
14:30-15:00	Barát János: Maximális k-metsző gráfok
15:00-15:30	Dósa György: Ládapakolási játékok
15:30-16:00	Szalkai István: Mindennapi geometriai élményeim, hatványösszegek a geometriában

Karoly Bezdek: Contact numbers for sphere packings

(Universities of Calgary and of Pannonia)

In discrete geometry, the contact number of a given finite number of non-overlapping spheres was introduced as a generalization of Newton's kissing number. This notion has not only led to interesting mathematics, but has also found applications in the science of self-assembling materials, such as colloidal matter. The talk is survey type focusing on the latest develop¬ments and listing a number of (new) conjectures.

 

Marko Jakovac: Secure sets in graphs

(University of Maribor)

The concept of a secure set is a generalization of defensive alliances in graphs. Defensive alli-ances are related to the defense of a single vertex. However, in a general realis¬tic settings, a defensive alliance should be formed so that any attack on the entire alliance or any subset of the alliance can be defended. In this sense, secure sets represent an attempt to develop a mo-del of this situation. Given a graph G=(V,E) and a set of vertices S subset of V, the set S is a secure set if it can defend every attack of vertices outside of S, according to an appropriate definition of »attack« and »defense« . The minimum cardinality of a secure set in G is the security number s(G). In this talk several results will be presented on the security number of graphs and graph products.

 

Istvan Szalkai: Computer Experiments on Contact Numbers of Ball Packings in Various Hexagonal and Octahedral Grids

(University of Pannonia)

We describe the structure of the different (!) hexagonal grids in dimension d=3, then investi-gate the contact numbers of ball packings in these and the octahedral grids up to 200 balls. http://arxiv.org/abs/1603.05390 , http://arxiv.org/abs/1611.06394

 

Zsolt Tuza: Choice identification in graphs

(Rényi Institute and University of Pannonia)

Let G be a graph. A set S of vertices is called an identifying set of G if there exists an injec¬ti-ve function f that maps each vertex of G to a nonempty subset of S, such that every vertex in f(v)-v is adjacent to v. (The vertex v itself may or may not belong to f(v).) The choice identi-fication number of G is the smallest cardinality of an identifying set. We compare this value with various parameters of G, and study the algorithmic complexity of determining it in seve-ral graph classes. This is joint work with Cristina Bazgan and Csilla Bujtás.

 

Bujtás Csilla: Gráfparaméterek becslése súlyok alkalmazásával

(Pannon Egyetem)

Ha súlyokat rendelünk egy gráf (vagy hipergráf) csúcsaihoz és\vagy éleihez, majd egy algorit-mus során a súlyokat lokális és globális tulajdonságok alapján változtatjuk, becsléseket adha-tunk különböző gráfparaméterek értékeire. Az első egyszerű alkalmazás azt mutatja, hogyan lehet ezzel a módszerrel új felső korlátot bizonyítani a gráfok játék-dominálási számára, majd bonyolultabb súlyozásra illetve más paraméterek becslésére is mutatunk példákat.

 

Barát János: Maximális k-metsző gráfok

(Pannon Egyetem)

Legyen C egy gráfosztály. Egy G gráf maximális C-re nézve, ha G benne van C-ben, de bár-mely G-ből hiányzó élet hozzáadva G-hez, a keletkezett gráf nincs benne C-ben. Természetes kérdés, hogy legfeljebb hány éle lehet egy C-beli gráfnak a csúcsszám függvényében. Például bármely n csúcsú síkgráfnak legfeljebb 3n-6 éle lehet. Ha kevesebb van, akkor tudunk hozzá-adni hiányzó éleket, amíg elérjük ezt a felső korlátot. Tekintsük most a k-metsző gráfokat, amelyekre az igaz, hogy lerajzolhatók a síkba úgy, hogy minden élet legfeljebb k másik él metsz. Vajon hány éle lehet egy maximális k-metsző gráf-nak? Ezt a kérdéskört járjuk körül. Nagyon meglepő dolgokat is tapasztalhatunk. (Tóth Gézával közös eredmények.)

 

Dósa György: Ládapakolási játékok

(Pannon Egyetem)

A ládapakolási játékok esetén adott valamilyen pakolás, és a tárgyak „igyekeznek” valami¬lyen számukra kedvezőbb módon pakolódni. Az ezzel kapcsolatos vizsgálatokat Bilo kezdte. Itt a tárgyak méretükkel arányosan „fizetnek” azért hogy egy ládában benne lehessenek, és ha egy tárgy át tud kerülni egy másik ládába úgy hogy ott kevesebbet fizet (befér oda, és miután odamegy, a tárgyak összmérete ővele együtt a megcélzott ládában nagyobb mint a jelenlegi ládájában), akkor a tárgy egy „önző lépést” tesz, átmegy oda. Kimutatható, hogy véges sok lépés után egyensúlyi helyzet (Nash Equilibrium, röviden NE) áll be, és az NE pakolás esetén a ládák száma legfeljebb 5/3-szorosa az optimális ládaszámnak. A feladatnak azóta többféle variánsa született, illetve különféle vizsgálatok folytak az egyensúlyi helyzetekkel kapcsolat-ban. Ezekről igyekszünk egy áttekintést nyújtani, bemutatva az ismert és új eredményeket, továbblépési lehetőségeket, nyitott kérdéseket is.

 

Szalkai István: Mindennapi geometriai élményeim, Hatványösszegek a geometriában

(Pannon Egyetem)

Néhány kevésbé közismert, hétköznapi geometriai jelenséget mutatok be és elemzek röviden, amivel a közelmúltban volt szerencsém találkozni. http://math.bme.hu/~hujter/160424.pdf , http://math.bme.hu/~hujter/161121.pdf Meglepő módon sok egyszerű geometriai feladatban megjelennek a negatív- és törtkitevős hatványösszegek, melyek a számtani, négyzetes és harmonikus közepek általánosításai. Pár ilyen feladatot mutatok be. http://math.bme.hu/~hujter/170201.pdf