Graphs, Groups, Configurations and Geometries  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
114614
Type NN
Principal investigator Szőnyi, Tamás
Title in Hungarian Gráfok, csoportok, konfigurációk és geometriák
Title in English Graphs, Groups, Configurations and Geometries
Keywords in Hungarian gráfok, csoportok, konfigurációk, geometriák
Keywords in English graphs, groups, configurations, geometries
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science (Eötvös Loránd University)
Participants Barát, János
Csikvári, Péter
Gévay, Gábor
Héger, Tamás
Kiss, György
Nagy, Gábor Péter
Nagy, Gábor Péter
Ruff, János
Sziklai, Péter
Starting date 2015-06-01
Closing date 2019-05-31
Funding (in million HUF) 19.260
FTE (full time equivalent) 12.40
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A tervezett kutatás alapvető célja geometriákból származó érdekes gráfosztályok színezési problémáinak (pl. projektív vagy affin terek fix dimenziós alterei által alkotott dizájnok fölső kromatikus száma és ennek kiegyensúlyozott változata), policiklikus konfigurációknak, konfigurációk szorzatának és szimmetriáinak, illetve ezek speciális területeinek vizsgálata. A legtöbb esetben pont-egyenes konfigurációkra ismertek eredmények, és ezeket terjesztenénk ki pont-kör konfigurációkra. Tervezzük geometriai egészautomorfizmusok vizsgálatának kiterjesztését affin síkokról terekre. Néhány esetben a véges geometria alkalmas a gráfelméletből és a Schur gyűrűk és CI csoportok elméletéből fakadó kérdések vizsgálatára. Példaként említhetjük, hogy a Payley-gráf automorfizmuscsoportjának meghatározása szorosan kapcsolódik Rédei elméletéhez hézagos polinomokról. További véges geometriai eredményeket tervezünk alkalmazni a C_p^n, n>3 csoportok fölötti p-Schur gyűrűk vizsgálatában. Folytatnánk az ívtranzitív bicirkulánsok tanulmányozását. Bizonyos feltételek mellett ezek dihedránsok is (azaz Cayley-gráfok egy diédercsoport fölött). Különös figyelmet kapnának a prímrendű ívtranzitív bicirkulánsok. Tanulmányoznánk és implementálnánk olyan algoritmusokat is, melyek adott G automorfizmuscsoportú A algebrákat keresnek. Kiemelten kezelnénk azon eseteket, amikor G vagy A további tulajdonságokkal rendelkezik, pl. G irreducibilis, vagy A antikommutatív. Ezt az algoritmust alkalmazni kívánjuk a legkisebb 2 exponensű Bol loop konstrukciójának vizsgálatában.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A pályázat keretében erősíteni szeretnénk az algebrai, geometriai és kombinatorikus technikák alkalmazását gráf-, csoport- és konfigurációelméleti, továbbá geometriai problémákban. Ez a szlovén és a magyar kutatócsoport geometriai és gráfelméleti tudásának megosztásával és ötvözésével lehetne elérni, tekintetbe véve a fiatal kutatók új kutatási területekbe való bevezetésének lehetőségét is. Meg vagyunk győződve arról, hogy a geometriában és a gráfelméletben hatalmas lehetőségek rejlenek a látszólag távol eső gyakorlati problémák kezelésére is. A korábbi gyüttműködések tapasztalata mutatja, hogy a különféle területeken dolgozó résztvevők készek közös munkára és új vizsgálatok indítására.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A tervezett együttműködés alapkutatási jellegű. Fő haszna a vizsgált témakörök mélyebb összefüggéseinek felderítése, megértése. Mindegyik résztvevő részt vesz az egyetemi képzésben, az eredmények egyik természetes hasznosítása a tananyagokba, speciális kurzusok témái közé való bekerülés.

További közvetlen haszon a kapcsolódó objektumok szerkezetének jobb megismerése. A csoportok-geometriák-polinomok a "természet" szimmetriáinak felkutatásában, az algebra, a geometria és a kombinatorika kapcsolatainak feltérképezésében nyújtanak segítséget. Egyes, általunk vizsgált objektumok a matematika, sőt, más természettudományok különféle területein is felbukkannak (pl. Cayley-gráfok, szimmetriacsoportok). Így az ezekről szóló eredmények megvilágíthatnak látszólag távoli területeket is.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A tervezett együttműködés alapkutatási jellegű. Fő haszna a vizsgált témakörök mélyebb összefüggéseinek felderítése, megértése. Mindegyik résztvevő részt vesz az egyetemi képzésben, az eredmények egyik természetes hasznosítása a tananyagokba, speciális kurzusok témái közé való bekerülés.

További közvetlen haszon a kapcsolódó objektumok szerkezetének jobb megismerése. A csoportok-geometriák-polinomok a "természet" szimmetriáinak felkutatásában, az algebra, a geometria és a kombinatorika kapcsolatainak feltérképezésében nyújtanak segítséget. Egyes, általunk vizsgált objektumok a matematika, sőt, más természettudományok különféle területein is felbukkannak (pl. Cayley-gráfok, szimmetriacsoportok). Így az ezekről szóló eredmények megvilágíthatnak látszólag távoli területeket is.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The basic questions of the proposed research are some specific topics about colorings of interesting classes of graphs coming from geometries (e.g. the upper chromatic number of designs coming from subspaces of fixed dimension of a projective and affine space and its balanced variants), polycyclic configurations, product and symmetries of configurations. In most cases there are results known for point-line configurations and we plan to extend the results for point-circle configurations. We also plan to extend the investigations of integral automorphisms of geometries to affine spaces from planes. In some cases finite geometry can be applied to problems coming from graph theory and the theory of Schur rings and CI groups. As an example we mention that determining the automorphism group of Paley graphs is strongly related to R'edei's theory of lacunary polynomials. We plan to apply further results from finite geometry in the investigation of $p$-Schur rings over groups C_p^n for$n > 3. We plan to study further arc-transitive bicirculants. Under certain conditions these graphs are also dihedrants (that is, Cayley graphs over a dihedral group). We plan to pay special attention to arc-transitive bicirculants of prime valency. We wish to study and implement algorithms which find one/all finite algebras $A$ with given automorhism group $G$. We are especially interested in cases when $G$ or $A$ have some extra properties; for example, when $G$ is irreducible or when $A$ is anti-commutative. As an application, we intend to use this algorithm to study the construction of the smallest simple Bol loop $Q$ of exponent 2.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
In the project we would like to strengthen the use of algebraic, geometric, and combinatorial techniques for problems about graphs, groups, configurations and geometries. This could be achieved by spreading knowledge of geometry and graph theory between the Slovenian and Hungarian research groups, and in particular, by giving opportunity to young researchers to get acquainted with new fields of research. We are convinced that geometry and graph theory have enormous potential when applied to practical problems that seem to be far away from it. Experience gathered from previous cooperation shows that participants working on different topics are ready to make joint works and start new investigations.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The project proposal is about pure theoretical research. Its main purpose is to understand the deep relations among the topics concerned. Each of the participants are university lecturers as well, one possible benefit of our results contains including them into our special MSc or PhD courses.

A further benefit is the better understanding of the structure of the related objects. Groups, geometries, polynomials play an important role in investigations of the symmetries of "nature", and in exploring links among Algebra, Geometry and Combinatorics. Some of the objects examined by our group arise in other topics in Mathematics, moreover in other fields of science (Cayley groups, symmetry groups). Hence our result may have implications in some other fields as well.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
The project proposal is about pure theoretical research. Its main purpose is to understand the deep relations among the topics concerned. Each of the participants are university lecturers as well, one possible benefit of our results contains including them into our special MSc or PhD courses.

A further benefit is the better understanding of the structure of the related objects. Groups, geometries, polynomials play an important role in investigations of the symmetries of "nature", and in exploring links among Algebra, Geometry and Combinatorics. Some of the objects examined by our group arise in other topics in Mathematics, moreover in other fields of science (Cayley groups, symmetry groups). Hence our result may have implications in some other fields as well.




 

Final report

  
Results in Hungarian
A kutatás fő témája gráfok, csoportok, geometriák, konfigurációk és kapcsolataik voltak. Geometriai struktúrákból jövő gráfok színezéseire meghatároztuk projektív terek felső kromatikus számát, valamint testre épített síkok kiegyenlített felső kromatikus számát. Becsléseket adtunk projektív és affin terek akromatikus és pszeudoakromatikus indexére és affin, biaffin síkok és általánosított négyszögek metrikus dimenziójára. Meghatároztuk affin terek egész automorfizmusait. Wegner 3-reguláris gráfokra vonatkozó sejtését igazoltuk általánosított Petersen gráfokra. Bevezettük az edge-girth regular gráfok fogalmát. Vizsgáltuk a Ryser-sejtést r-részes, r-uniform hipergráfokra. Számos eredmény született a Miquel-konfigurációl és feloldható konfigurációkról. Vizsgáltuk, hogy mely gráfok párosítási polinomjának minden gyöke egész, a problémát teljesen megoldottuk, ha a gráfnak van Hamilton-köre vagy reguláris vagy karommentes. Vizsgáltuk a függetlenségi polinom gyökmentes tartományát, továbbá gráfok irányításainak és faktorainak számát. Bizonyítottuk a Sidorenko-sejtés egy determinánsos változatát. Az 1-planar gráfok esetében megmutattuk, hogy minden maximális ilyen n csúcsú gráfnak legalább 2.22n éle van. Stabilitási tételeket bizonyítottunk k mod p multihalmazokra, és ennek kódelméleti alkalmazását adtuk. Új hemisystem-eket konstruáltunk Hermite-felületeken algebrai görbék segítségével. Vizsgáltuk multinetek projektív síkba ágyazását és Hall-síkok öröklött hiperoválisait is.
Results in English
Our research focused on groups, graphs, geometries, configurations and their connections. For colorings of graphs coming from geometries we determined the upper chromatic number of projective spaces, and the balanced upper chromatic number of Desarguesian planes. We gave estimates on the achromatic and pseudoachromatic index of projective and affine spaces, and the metric dimension of affine, biaffine planes and generalized quadrangles. We determined integral automorphisms of affine spaces. We proved Wegner's conjecture about cubic graphs for generalized Petersen graphs. We introduced the notion of edge-girth regular graphs. We investigated Ryser's conjecture on r-partite, r-uniform hypergraphs. We obtained several results about the Miquel configuration and resolvable configurations. We studied graphs whose matching polynomial has only integer zeros, the problem was completely solved if G has a Hamiltonian cycle or regular or claw-free. We also studied the zero-free region of the independence polynomial and the number of orientations and factors of a graph. We proved a variant of Sidorenko's conjecture about determinants. In case of 1-planar graphs, we proved that any maximal such graph on n vertices must has at least 2.22n edges. We proved stability theorems for k mod p multisets and applied it for codes. We constructed new hemisystems on Hermitian surfaces using curves. We studied embeddings of multinets in projective planes and inherited hyperovals in Hall planes.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=114614
Decision
Yes





 

List of publications

  
Jan De Beule, Jeroen Demeyer, Sam Mattheus, Péter Sziklai: On the cylinder conjecture, Designs, Codes and Cryptography (2019) 87:879–893, 2019
F. Bencs, P. Csikvári: Note on the zero-free region of the hard-core model, submitted manuscript, 2019
M. Borbényi, P. Csikvári: Counting degree-constrained subgraphs and orientations, Submitted manuscript, 2019
P. Csikváry, A. Imolay: Covers, orientations and factors, submitted manuscript, 2019
G. Gévay, N. Bašić, J. Kovič, T. Pisanski: Point-ellipse and some other exotic configurations, submitted manuscript, 2019
G. Gévay, I. Hafner, T. Pisanski: Graph of a Six-Cube and Skeleton of a Rhombic Triacontahedron, Wolfram Demonstrations Project, 2019
N. Bogya, G. P. Nagy: Light dual multinets of order six in the projective plane, Acta Math. Hungar., article in press, 2019
Gábor Korchmáros, Gábor P. Nagy: Graphical Frobenius representations of non-abelian groups, submitted manuscript, 2019
Gy. Kiss, T. Szőnyi: Finite Geometries, CRC Press - Taylor & Francis Group, Boca Raton, 338 p., 2019
János Barát, Gábor N. Sárközy: Partitioning 2-Edge-Colored Ore-Type Graphs by Monochromatic Cycles, J. Graph Theory, 81 (2016), 317-328, 2016
R. Aharoni, J. Barát, I. M. Wanless: Multipartite Hypergraphs Achieving Equality in Ryser’s Conjecture, Graphs and Combinatorics 32 (2016), 1-15, 2016
István Kovács, Klavdija Kutnar, János Ruff, Tamás Szőnyi: Integral authomorphisms of affine spaces over finite fields, Designs, Codes and Cryptography 84:181, 2017
S. Akbari, P. Csikvári, A. Ghafari, S. Khalashi Ghezelahmad, M. Nahvi: Graphs with Integer Matching Polynomial Roots, Discrete Applied Mathematics 224, 1-8, 2017
János Barát, Géza Tóth: Improvements on the density of maximal 1-planar graphs, J. Graph Theory, 88:1, 101-109, 2018
Dávid Mezőfi, Gábor Péter Nagy: The GAP4 package UnitalSZ, GitHub, 2018
Gábor Péter Nagy: Doubly transitive sets of even permutations., Bul. Acad. Ştiinţe Repub. Mold. Mat. 80:1, 78–82., 2016
Gábor Korchmáros, Gábor Péter Nagy: Group-labeled light dual multinets in the projective plane., Discrete Math. 341:8, 2121–2130., 2018
Gábor Gévay: An extension of Miquel's six-circles theorem, Forum Geometricorum 18, 115--118., 2018
Gábor Gévay: Pascal's triangle of configurations., M. Conder, A. Deza and A. Ivic Weiss (Eds.), Discrete Geometry and Symmetry, Springer., 2018
Robert Jajcay, György Kiss, Štefko Miklavič: Edge-girth-regular graphs, European J. Combin. 72, 70--82., 2018
Tamás Szőnyi, Zsuzsa Weiner: Stability of k mod p multisets and small weight codewords of the code generated by the lines of PG(2,q), Journal of Combinatorial Theory, Series A vol. 157, 321--333, 2018
Aart Blokhuis, István Kovács, Gábor Péter Nagy, Tamás Szőnyi: Inherited conics in Hall planes, submitted, 2018
Gábor Korchmáros, Gábpr Péter Nagy, Pietro Speziali.: Hemisystems of the Hermitian Surface, submitted, 2018
Gábor Gévay: A remarkable theorem on eight circles, accepted for publication in Forum Geometricorum, 2018
Gábor Gévay: Resolvable configurations, submitted, 2018
Daniele Bartoli, Tamás Héger, György Kiss, Marcella Takáts: On the metric dimension of affine planes, biaffine planes, and generalized quadrangles, accepted for publication in Australasian J. Combin., 2018
Gabriela Araujo-Pardo, György Kiss, Christian Rubio-Montiel, Adrián Vázquez-Ávila: On line colorings of finite projective spaces, accepted for publication in Electron. J. Combin, 2018
Gabriela Araujo-Pardo, György Kiss, Christian Rubio-Montiel, Adrián Vázquez-Ávila: On chromatic indices of finite affine spaces, accepted for publication in Ars Math. Contemp., 2018
Daniele Bartoli, György Kiss, Stefano Marcugini, Fernanda Pambianco: Resolving sets in higher dimensional projective spaces, submitted for Electron. J. Combin., 2018
Péter Csikvári, Balázs Szegedy: On Sidorenko's conjecture for determinants and Gaussian Markov random fields, submitted, 2018
Péter Csikvári: Statistical matching theory, submitted, 2018
Ahmad Abu-Khazneh, János Barát, Alexey Pokrovskiy, Tibor Szabó: A family of extremal hypergraphs for Ryser's conjecture, submitted for J. Combin. Theory A, 2018
János Barát: Decomposition of cubic graphs related to Wegner's conjecture, submitted, 2018
János Barát: On the number of edges in a K_5-minor-free graph of given girth, submitted, 2018
János Barát, Géza Tóth: Improvements on the density of maximal 1-planar graphs, J. Graph Theory, 88:1, 101-109, 2018
Gábor Péter Nagy: Doubly transitive sets of even permutations, Bul. Acad. Ştiinţe Repub. Mold. Mat. 80:1, 78–82., 2016
Aart Blokhuis, István Kovács, Gábor Péter Nagy, Tamás Szőnyi: Inherited conics in Hall planes, Disc. Math. 342:4, 1098-1107, 2019
Gábor Korchmáros, Gábor Péter Nagy, Pietro Speziali: Hemisystems of the Hermitian Surface, J. Combin. Theory Ser. A 165, 408-439, 2019
Gábor Gévay: Resolvable configurations, Discrete Applied Mathematics 266, 319-330, 2019
Daniele Bartoli, Tamás Héger, György Kiss, Marcella Takáts: On the metric dimension of affine planes, biaffine planes, and generalized quadrangles, Australasian J. Combin. 72, 226-248, 2018
Gabriela Araujo-Pardo, György Kiss, Christian Rubio-Montiel, Adrián Vázquez-Ávila: On line colorings of finite projective spaces, submitted manuscript, 2018
Gabriela Araujo-Pardo, György Kiss, Christian Rubio-Montiel, Adrián Vázquez-Ávila: On chromatic indices of finite affine spaces, Ars Math. Contemp. 16, 67-79, 2019
Péter Csikvári, Balázs Szegedy: On Sidorenko's conjecture for determinants and Gaussian Markov random fields, submitted manuscript, 2018
Ahmad Abu-Khazneh, János Barát, Alexey Pokrovskiy, Tibor Szabó: A family of extremal hypergraphs for Ryser's conjecture, J. Combin. Theory A 161, 164-177, 2019
János Barát: Decomposition of cubic graphs related to Wegner's conjecture, Discrete Mathematics 342:5, 1520-1527, 2019
Z. L. Blázsik, T. Héger, T. Szőnyi: On the upper chromatic number and multiple blocking sets of PG(n,q), J. Comb. Des., 2019
J. Barát, Z. L. Nagy: Transversals in generalized latin squares, Ars Mathematica Contemporanea 16, 39-47, 2019
P. Csikvári: Extremal regular graphs: the case of the infinite regular tree, submitted manuscript, 2019
P. Csikvári: Statistical Matching Theory, Building Bridges II, 2019




 

Events of the project

  
2016-12-15 15:21:22
Résztvevők változása



Back »