Extremális kombinatorika és véges geometriák  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
81310
típus K
Vezető kutató Szőnyi Tamás
magyar cím Extremális kombinatorika és véges geometriák
Angol cím Extremal combinatorics and finite geometries
magyar kulcsszavak véges geometriai konstruckiók, extremális strukturák stabilitása, algebrai módszerek
angol kulcsszavak finite geometry constructions, stability of extremal structures, algebraic methods
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Kombinatorika
zsűri Matematika–Számítástudomány
Kutatóhely Számítógéptudományi Tanszék (Eötvös Loránd Tudományegyetem)
résztvevők Csajbók Bence
Csikvári Péter
Fancsali Szabolcs
Héger Tamás
Kiss György
Lőrinczné Takáts Marcella
Maloschikné Harrach Nóra Viola
Nagy Zoltán Lóránt
Sziklai Péter
Weiner Zsuzsanna
projekt kezdete 2010-03-01
projekt vége 2014-06-30
aktuális összeg (MFt) 18.000
FTE (kutatóév egyenérték) 8.16
állapot lezárult projekt
magyar összefoglaló
A pályázat célja olyan problémák vizsgálata, melyekhez véges geometriai és extremális kombinatorikai ismeretekre is szükség van.
Az extremális kombinatorikai becslések élességét sokszor mutatják geometriai konstrukciók, másrészt sokszor az optimális struktúra pontos ismerete segítséget nyújthat az éles becslés bizonyításában. Az éles becslések mellett számtalan stabilitási eredmény is ismert halmazrendszerekről és gráfokról, ezeknek természetes módon fogalmazható meg az analogonja véges testek feletti vektorterekben, illetve véges geometriákban.

Kicsit általánosabban, extremális és stabilitási kérdéseket akarunk vizsgálni véges testekben, illetve ezek által koordinátázott struktúrákban, valamint gráfok spektrumával kapcsolatban.

Kombinatorikai és geometriai módszerek mellett a felhasznált eszközök elsősorban algebraiak: a polinom módszer, illetve annak az utóbbi 15 évben véges geometriákra kifejlesztett megfelelői (algebrai görbék pozitív karakterisztikában, rezultánsok, hatványösszegek) mellett algebrai gráfelméleti módszerekre lesz szükség.
angol összefoglaló
We plan to study problems, for which both finite geometrical and extremal combinatorial knowledge is important. In extremal combinatorics there are many cases, where the sharpness of a bound is shown by a construction based on finite geometries, on the other hand, sometimes understanding the combinatorial properties of the extremal structures helps to find the proof of the conjectured bound. Besides these, there are several stability results about extremal set systems, for which there is a natural analogue for vectorspaces over finite fields or in finite geometries.

In a somewhat more general setting, we also want to study extremal and stability problems in finite fields, geometries over finite fields and about the spectra of graphs.

Besides combinatorial and geometrical tools, techniques to be used are mainly algebraic: the polynomial method and its variants developed in the last decade for finite geometries (algebraic curves in positive characteristics, resultants, power sums) and methods of algerbaic graph theory.




 

Zárójelentés

  
kutatási eredmények (magyarul)
A projektben extremális kérdésekkel, klasszikus kombinatorikai eredmények vektortér analogonjaival, illetve véges geometrián belül ponthalmazokra vonatkozó extremális kérdésekkel foglalkoztunk. A Turán-probléma sűrűségi változatát vizsgálva meghatároztuk fákra azon kritikus élsűrűséget, amely garantálja H egy felfújtjában H megjelenését. Tetszőleges gráfra jó becslést adtunk ezen élsűrűségre a legnagyobb fokszám függvényében. Algebrai módszerekkel leírtuk az összes, PG(2,q) illeszkedési gráfjának feszített részgráfjaként előálló k-reguláris, 6 bőségű gráfot, ha q-k kicsi. Leírtuk néhány (általánosított) q-Kneser gráf elég nagy független halmazait, amiből bizonyos esetekben a kromatikus számot is meghatároztuk. Megmutattuk, hogy a kombinatorikus keresés vektortér analogonjára különbözik az adaptív és a nem-adaptív eset. A q-analógiát használtuk neves azonosságok igazolására is. Nagyon általános módszert adtunk arra, hogy egy hipersíknál kicsit kisebb ponthalmaz kiegészíthető hipersík méretűvé úgy, hogy a meghatározott irányok halmaza ugyanaz maradjon, hacsak ezen irányok halmaza nem nagyon speciális struktúrájú. Stabilitási eredményeket igazoltunk q-hoz közeli méretű halmazokat metsző egyenesek számára és kis Kakeya-halmazokra páros karakterisztikában. Meghatároztuk, ill. megbecsültük projektív síkok és terek felső kromatikus számát és ennek változatait. Karakterizáltuk PG(2,q) bizonyos, nagy kollineáris részt tartalmazó szemiíveit.
kutatási eredmények (angolul)
In the project we studied extremal questions, q-analogues of classical combinatorial results and, inside finite geometry, extremal questions for sets of points. Studying the density version of Turán's problem, the critical edge-density guaranteeing the appearance of H in a blownup graph of H was determined for trees. In the general case we gave a good bound on the critical density in terms of the maximum degree. Usingalgebraic methods we described all induced k-regular graphs of girth 6 of the incidence graph of PG(2,q) when q-k is small. We classified large cocliques of some (generalized) q-Kneser graphs, and in some cases also their chromatic number was determined. We showed that the q-analogue of the classical combinatorial search behaves differently in the adaptive and the non-adaptive case. We used q-analogy to give a short proof of some famous identities. We developed a very general method for the extendability of a set having a little fewer points than a hyperplane into a set of size of a hyperplane without changing the set of directions determined, unless the set of determined directions has a very special structure. We obtained stability results for the number of lines meeting a set of size close to q and for small Kakeya sets in even characteristic. We found or bounded the upper chromatic number (and some of its variants) of projective planes and spaces. We characterized particular semiarcs of PG(2,q) containing a large collinear subset.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=81310
döntés eredménye
igen





 

Közleményjegyzék

  
N. V. Harrach, K. Metsch, T. Szőnyi, and Zs. Weiner,: Small point sets of PG$(n, p^{3h})$ intersecting each line in $1 \bmod p^h$ points., J. Geom. 98 (2010), 59-78, 2010
Z. L. Nagy: A Multipartite Version of the Turan Problem - Density Conditions and Eigenvalues, The Electronic J. Combinatorics, Vol 18(1), P46,, 2011
Csajbók B. és Kiss Gy: Notes on semiarcs, Mediterr. J. Math. 9, 677-692, 2012
Kiss Gy.: Latin négyzetek, szép sudoku megoldások és véges geometriák I.-II.,, Középiskolai Matematikai és Fizikai Lapok 60 (2010), 130-136 és 194-200, 2010
T. Szőnyi, Zs. Weiner: A stability theorem for lines in Galois planes of prime order, Designs, Codes, and Cryptography 62, 103-108, 2012
A. Blokhuis, A. E. Brouwer, T. Szőnyi: On the chromatic number of q-Kneser graphs, Designs, Codes, and Cryptography 65, 187-197, 2012
Weiner Zsuzsa, Szőnyi Tamás: Proof of a conjecture of Metsch, J. Combin. Theory Ser. A 118, 2066-2070, 2011
A. Blokhuis, A.E. Brouwer, T. Szőnyi, Zs. Weiner: q-analogues and stability, Journal of Geometry 101, 31-50, 2011
P. Csikvári: Applications of the Kelmans transformation: extremality of the threshold graphs, he Electronic Journal of Combinatorics 18, P182., 2011
P. Csikvári: Two remarks on the adjoint polynomial, European Journal of Combinatorics 33, 583-591, 2012
P. Csikvári and M. R. Oboudi: On the roots of the edge cover polynomial, European Journal of Combinatorics 32 (8), 1407-1416., 2011
P. Csikvári, Z. L. Nagy: The Density Turán problem, Combinatorics, Probability and Computing 21, 531-553, 2012
Fancsali Szabolcs Levente: Bounds and spectrum results in Galois geometry and coding theory, Eötvös Loránd University, PhD thesis, 2012
P. Sziklai, M. Takáts: A generalization of the direction problem, Discrete Mathematics, 312, 2083-2087, 2012
Sz. Fancsali, P. Sziklai, M. Takáts: On the number of directions determined by less than q points, Journal of Algebraic Combinatorics 37, 27-37, 2013
Damásdi, G., Héger, T., Szőnyi, T.: The Zarankiewicz problem, cages, and geometries, Annal Univ. Bud. Rolando Eötvös, megjelenőben, 2013
Bacsó, G., Héger, T., Szőnyi, T.: The 2-blocking number and the upper chromatic number of PG(2,q), Journal of Combinatorial Designs, elfogadva, 2013
Harrach, Nóra V.: Unique reducibility of multiple blocking sets, Journal of Geometry 103, 445-456, 2012
Jan De Beule, Péter Sziklai, Marcella Takáts: On the structure of the directions not determined by a large affine point set, Journal of Algebraic Combinatorics, elfogadva, 2013
P. Sziklai, G. Van de Voorde: A small minimal blocking set in PG(n,p^t), spanning a (t-1)-space, is linear, Designs, Codes, and Cryptography, elfogadva, 2013
A. Gács, T. Héger, Zs. Weiner: On $(k,6)$-graphs arising from projective planes, European Journal of Combinatorics 34, 285-296, 2013
T. Héger, M. Takáts: Resolving sets and semi-resolving sets in finite projective planes, Electronic J.~Comb. 19, issue 4, 2012
P. Sziklai: Applications of polynomials over finite fields, MTA doktori, 2013
Z. L. Nagy, L. Özkahya, B. Patkós, M. Vizer: On the ratio of maximum and minimum degree in maximal degree in maximal intersecting families, Discrete Math. 313, 207-211, 2013
Gy. Károlyi, Z. L. Nagy: A short proof for Andrews' q-Dyson conjecture, Proc. Amer. Math. Soc. elfogadva, 2013
P. Csikvári: Note on the smallest root of the independence polynomial, Combinatorics, Probability and Computing 22, 1-8, 2013
P. Csikvári: On a poset of trees II, J Graph Theory, elfogadva, 2013
N. V. Harrach, K. Metsch, T. Szőnyi, and Zs. Weiner,: Small point sets of PG$(n, p^{3h})$ intersecting each line in $1 \bmod p^h$ points., J. Geom. 98 (2010), 59-78, 2010
Csajbók B. és Kiss Gy: Notes on semiarcs, Mediterr. J. Math. 9, 677-692, 2012
T. Szőnyi, Zs. Weiner: A stability theorem for lines in Galois planes of prime order, Designs, Codes, and Cryptography 62, 103-108, 2012
Weiner Zsuzsa, Szőnyi Tamás: Proof of a conjecture of Metsch, J. Combin. Theory Ser. A 118, 2066-2070, 2011
A. Blokhuis, A.E. Brouwer, T. Szőnyi, Zs. Weiner: q-analogues and stability, Journal of Geometry 101, 31-50, 2011
Fancsali Szabolcs Levente: Bounds and spectrum results in Galois geometry and coding theory, Eötvös Loránd University, PhD thesis, 2012
P. Sziklai, M. Takáts: A generalization of the direction problem, Discrete Mathematics, 312, 2083-2087, 2012
Sz. Fancsali, P. Sziklai, M. Takáts: On the number of directions determined by less than q points, Journal of Algebraic Combinatorics 37, 27-37, 2013
Damásdi, G., Héger, T., Szőnyi, T.: The Zarankiewicz problem, cages, and geometries, Annales Univ. Bud. Rolando Eötvös, 56, 3-37, 2013
Bacsó, G., Héger, T., Szőnyi, T.: The 2-blocking number and the upper chromatic number of PG(2,q), Journal of Combinatorial Designs, 21, 585-602., 2013
Jan De Beule, Péter Sziklai, Marcella Takáts: On the structure of the directions not determined by a large affine point set, Journal of Algebraic Combinatorics, 38, 888-899., 2013
P. Sziklai, G. Van de Voorde: A small minimal blocking set in PG(n,p^t), spanning a (t-1)-space, is linear, Designs, Codes, and Cryptography, 68, 25-32., 2013
A. Gács, T. Héger, Zs. Weiner: On $(k,6)$-graphs arising from projective planes, European Journal of Combinatorics 34, 285-296, 2013
T. Héger, M. Takáts: Resolving sets and semi-resolving sets in finite projective planes, Electronic J.~Comb. 19, issue 4, 2012
Gy. Károlyi, Z. L. Nagy: A short proof of the Zeilberger-Bressoud q-Dyson theorem, Proc. Amer. Math. Soc. 142, 3007-3011., 2014
P. Csikvári: On a poset of trees II, J Graph Theory, 74, 81-103, 2013
A. Blokhuis, A.E. Brouwer, T. Szőnyi: Maximal cocliques in the Kneser graph on point-line flags in PG(4,q), European J. Combin. 35, 95-104, 2014
T. Szőnyi, Zs. Weiner: On the stability of small blocking sets, Journal of Algebraic Combinatorics 40, 279-292, 2014
Sz. L. Fancsali, P. Sziklai: Lines in higgledy-piggledy arrangement, Electronic J. Combinatorics 21 P 2.56, 2014
P. Csikvári, P. Frenkel: Benjamini-Schramm continuity of root moments of graph polynomials, European Journal of Combinatorics, elfogadva, 2014
M. Abért, P. Csikvári, P. Frenkel, G. Kun: Matchings in Benjamini-Schramm convergent graph sequences, Trans. Amer. Math. Soc., elfogadva, 2014
Z. L. Nagy: Permutations over cyclic groups, European J. Comb. 41C, 68-78, 2014
Kiss György, C. Rubio-Montiel: On m-factorizations of complete multigraphs and designs, Ars Math. Contemporanea, elfogadva, 2015
Csajbók Bence, Héger Tamás, Kiss György: Semiarcs with a long secant in PG(2,q), Innov. Incidence Geom., elfogadva, 2015
Daniele Bartoli, György Kiss, Stefano Marcugini, Fernanda Pambianco: 2-semiarcs in PG(2,q), Ars Combinatoria, elfogadva, 2015
Csajbók Bence: Semiarcs with long secants, Electronic J. Combinatorics 21, P 1.60, 2014
S. Ball, C. Padro, Zs. Weiner, C. Xing: On the representability of the biuniform matroid, SIAM J. Discrete Mathematics 27, 1482-1491, 2013
Harrach Nóra Viola: Blocking sets in finite projective spaces, http://teo.elte.hu/minosites/ertekezes2013/maloschikne_harrach_n_v.pdf, 2014
Héger Tamás: Some graph theoretic aspects of finite geometries, http://teo.elte.hu/minosites/ertekezes2013/heger_t.pdf, 2014
Csajbók Bence: Some new results on semiarcs in finite projective planes and on inverse-closed subsets in fields, Potenza, 2014
Héger Tamás, Patkós Balázs, Takáts Marcella: Search problems in vector spaces, Designs, Codes and Cryptography, elfogadva, 2014




 

Projekt eseményei

  
2012-07-26 11:35:48
Résztvevők változása
2012-06-15 13:42:14
Résztvevők változása



vissza »