Set Theory; Partition Calculus , Theory of Infinite Graphs
magyar kulcsszavak
halmazelmélet, partició kalkulus, gráfelmélet
angol kulcsszavak
set theory, partition calculus, graph theory
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)
100 %
zsűri
Matematika–Számítástudomány
Kutatóhely
HUN-REN Rényi Alfréd Matematikai Kutatóintézet
résztvevők
Erdos Péter Farkas Barnabás Juhász István Patkós Balázs Sági Gábor Soukup Lajos Szentmiklóssy Zoltán
projekt kezdete
2007-07-01
projekt vége
2011-07-31
aktuális összeg (MFt)
17.948
FTE (kutatóév egyenérték)
2.64
állapot
lezárult projekt
magyar összefoglaló
Klasszikus és új, kombinatorikus jellegű, halmazelméleti kérdéseket vizsgálunk kombinatorikus és matematikai logikai eszközökkel.
Megkiséreljük javitani a klasszikus Erdős-Rado tétel azon általánositásaira vonatkozó Foreman-Hajnal es Shelah féle eredményeket, melyekben az alaphalmaz számossága valamely nagy számossag rákövetkezője, és a homogén halmazok rendtipusai rendszámok.Ezek felhasználásával a kontinuum rákövetkezőjére és más ''kis'' számosságokra vonatkozó konzisztencia eredményeket akarunk nyerni.
Folytatni kivánjuk a - Hajnal által újabban meginditott - az erős negativ feltételeknek eleget tevő 2-particiók ''szivárvány'' részhalmazaira vonatkozó vizsgálatokat. Ezek a vizsgálatok szoros kapcsolatban vannak Shelah es Todorcevic korábbi - ZFC-ben bizonyitott - negativ partició tételeivel. Az előzetes eredményekről kivonat jelent meg.
Harmadik tárgykörünkben Soukup a pcf-elmélet felhasználásával bizonyitott számosság invariansokra vonatkozó eredményeit kivánjuk általánositani. A spektrum vizygálata azért előnyös, mert a spektrumok stabilabbak az alapmodell bővítéseire nézve, így jobb esélyünk van rájuk vonatkozó ZFC tételeket bizonyítani.
Negyedik tárgykörünk többet ölel fel. Ebben véges gráfokra vonatkozó egyszerű tételeket kivánunk végtelen gráfokra átvinni. Az eset amellyel részletesen foglalkozunk Chvatal es Lovász következő eredménye: Bármely véges $G$ irányitott gráfban van olyan független $A$ részhalmaz, amelyből $G$ minden pontjába vezet legfeljebb kettő hosszúságu út, azaz $G$-nek van kvázi-magja. P.L. Erdős es Soukup fogalmazták meg a következő sejtést: Tetszőleges $G$ gráf szögponthalmaza felbomlik két diszjunkt halmazra, melyek közül az egyiken $G$-nek, a másikon $G$ inverzének létezik kvázi-magja. Egy készülő hármas cikkben már számos részeredményt bizonyitunk.
angol összefoglaló
We are going to investigate several classical and new set theoretical problems of combinatorial character using both combinatorial methods and consistency proofs.
We will try to improve existing results of Foreman-Hajnal and Shelah for the generalization of the classical Erdős-Rado theorem for successors of large cardinals with ordinal goals. We intend to get from them stronger consistency results for the successor of the continuum and other`small' cardinals.
We investigate problems, raised by the PI recently, for the existence of rainbow subsets of 2-partitions satisfying strong negative square- bracket relations. This questions are intimately connected with ZFC results of Shelah and Todorcevic on the existence of negative square bracket relations. A preprint of preliminary results was written recently.
A third topic: Soukup used pcf-theory to prove some closure properties of certain cardinal invariants in ZFC. The investigation of spectra has the advantage that the spectrum is more stable concerning extensions of models, so we have a better chance to prove ZFC theorems about them.. There is hope that his results can be extended for many other invariants.
Our fourth topic is more comprehensive. We would like to work on transfer methods to generalize simple theorems of finite graph theory to infinite graphs. A case in point is a generalization of the following result of Chvatal and Lovasz: For a finite directed graph $G$ there is an independent subset $A$ of the vertices such that a path of length at most 2 leads to every vertex from a vertex of A i.e. G has a quasi-kernel. P.L.Erdős and Soukup formulated the conjecture that for every directed G there is a disjoint partition of the vertices to two sets such that on one of them G and on the other G inverse has a quasi kernel. In a triple paper we already have many partial results on this.
Zárójelentés
kutatási eredmények (magyarul)
Előzetes tervünknek megfelelően a halmazelmélet alábbi területein végeztünk kutatást és értünk el számos eredményt:
I. Kombinatorika
II. A valósak számsosságinvariánsai és ideálelmélet
III. Halmazelméleti topológia
Ezek mellett Sági Gábor kiterjedt kutatást végzett a modellelmélet területén , amely eredmények kapcsolódnak
a kombinatorikához is.
Eredményeinket 38 közleményben publikáltuk, amelyek majdnem mind az adott terület vezető nemzetközi lapjaiban jelentel meg (5 cikket csak benyújtottunk). Számos nemzetközi konferencián is résztvettünk,
és hárman közűlünk (Juhász, Sádi, Soukup) plenáris/meghívott előadók voltak számos alkalommal.
kutatási eredmények (angolul)
Following our research plan, we have mainly done research -- and established
a number of significant results -- in several areas of set theory:
I. Combinatorics
II. Cardinal invariants of the continuum and ideal theory
III. Set-theoretic topology
In addition to these, G. Sági has done extended research in model theory that
had ramifications to combinatorics.
We presented our results in 38 publications, almost all of which appeared or will appear in the
leading international journals of these fields (5 of these papers have been submitted but not accepted
as yet). We also participated at a number of international conferences, three
of us (Juhász, Sági, Soukup) as plenary and/or invited speakers at many of these.
I. Juhász and M. Magidor,: On maximal resolvability of monotonically normal spaces, Israel J. Math., to appear, 2012
Hajnal, András ; Larson, Jean A: Partition relations., Handbook of set theory. Vols 1,2,3, 129-213, Springer, Dordrecht,, 2010
Martinez JC; Soukup L: Superatomic Boolean algebras constructed from strongly unbounded functions,, Mathematical Logic Quarterly, to appear, 2011
Soukup L: Wide scattered spaces and morasses,, TOPOLOGY AND ITS APPLICATIONS 158:(5) pp. 697-707. (2011), 2011
Erdős, Péter L., Stoyle, Jens, and Soukup, Lajos:: Balanced Vertices in Trees and a Simpler Algorithm to Compute the Genomic Distance, APPLIED MATHEMATICS LETTERS 24: pp. 82-86. (2011), 2011
Erdős, Péter L., Miklosi, Istvan, and Soukup, Lajos:: Towards random uniform sampling of bipartite graphs with given degree sequence,, Combinatorics , Probability and Computing, benyujtva, 2011
Juhász I; Weiss W: On the convergence and character spectra of compact spaces, Fund. Math. 207 (2010), no. 2, 179--196., 2010
Dzamonja M; Juhász I;: CH, a problem of Rolewicz, and bidiscrete systems, Top. Appl, megjelenes alatt, 2011
Juhász I: Ken Kunen, the set-theoretic topologist, Top. Appl, megjelenes alatt, 2011
Juhász, István, Koszmider, Piotr, and Soukup, Lajos: A first countable, initially {$\omega_1$}-compact but non-compact space, Topology Appl. 156 (2009), no. 10, 1863--1879., 2009
Sagi G: Polyadic algebras, in "Cylindric-like algebras", ed H. Andreka, M. Ferenczi, I. Nemeti, megjelenes alatt, 2012
Goldstern M, Sagi G, Shelah S: Clones above the unary clone, Discrete Mathematics, submitted, 2012
Sagi G: Vaught's conjecture from the perspective of algebraic logic, Math. Log. Quarterl, 2012
Sagi G, Sziraki D: Some variants of Vaught's conjecture from the prespective of algebraic logic, Logic Journal of IGPL, 2012
Soukup L: Pcf theory and cardinal invariants of the reals., COMMENTATIONES MATHEMATICAE UNIVERSITATIS CAROLINAE 52:(1) pp. 153-162. (2011), 2011
Soukup L: Elementary submodels in infinite combinatorics., DISCRETE MATHEMATICS, to appear, 2011
Fuchino Sakaé, Geschke Stefan, Soukup Lajos: How to drive our family mad?, ARCHIVE FOR MATHEMATICAL LOGIC to appear, 2011
Farkas B: Hechler's theorem for tall analytic P-ideals, Journal of Symbolic Logic 76 (2011), no 2, pages 729-736., 2011
Borodulin-Nadzieja P, Farkas B: Cardinal coefficients associated to certain orders on ideals, ?, benyujtva, 2012
Soukup L: Infinite Combinatorics: From Finite to Infinite, HORIZONS OF COMBINATORICS Bolyai Society Mathematical Studies, 2008, Volume 17, 189-213,, 2008
Elekes M; Mátrai T; Soukup L: On splitting infinite-fold covers, Fund. Math. 212 (2011), 95-127, 2011
Erdős LP; Soukup L: No finite-infinite antichain duality in the homomorphism poset D of directed graphs, ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 27:(3) pp. 317-325. (2010), 2010
Martinez JC; Soukup L: The D-property on unions of scattered spaces, Topology Appl. 156(18), volume 156, Elsevier, 3086–3090, 2009, 2009
Sagi G: A short proof for the completeness of paramodulation, Bulletin of the Section of Logic, 2009
Juhász I; Szentmiklóssy Z: Interpolation of kappa-compactness and PCF theory, Comment. Math. Univ. Carolin. 50 (2009), no. 2, 315--320., 2009
Martinez JC; Soukup L: Cardinal sequences of LCS spaces under GCH, Ann. Pure Appl. Logic 161, volume 161, 1180–1193, 2010, 2010
Hajnal, András, Juhász, István, Soukup, Lajos, and Szentmiklóssy, Zoltán: Conflict free colorings of (strongly) almost disjoint set-systems, ACTA MATHEMATICA HUNGARICA 130: pp. 1-45. (2011), 2011
Fuchino, Sakaé, Juhász, István, Soukup, Lajos, Szentmiklóssy, Zoltán, and Usuba, Toshimichi:: Fodor-type Reflection Principle, metrizability and meta-Lindelofness, TOPOLOGY AND ITS APPLICATIONS 157:(8) pp. 1415-1429. (2010), 2010
Sagi G: Completeness of Paramodulation and Equational Logic,, Proceedings of the Tenth International Conference on Informatics, 2009
Sagi G: Absolutely Ubiquitous Structures and \aleph_0-stability,, Bulletin of the Section of Logic,, 2010
Sagi G: On nonrepresentable G-Polyadic algebras with representable cylindric reducts,, Journal of IGP, 2010
Farkas B: Forcing indestructible extensions of MAD families, Acta Univ. Carolin. Math. Phys. 51 (2010), suppl., pages 9-12.,, 2010