Set Theory; Partition Calculus , Theory of Infinite Graphs  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
68262
Type K
Principal investigator Hajnal, András
Title in Hungarian Halmazelmélet; Partíció kalkulus, Végtelen gráfok elmélete
Title in English Set Theory; Partition Calculus , Theory of Infinite Graphs
Keywords in Hungarian halmazelmélet, partició kalkulus, gráfelmélet
Keywords in English set theory, partition calculus, graph theory
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Erdos, Péter
Farkas, Barnabás
Juhász, István
Patkós, Balázs
Sági, Gábor
Soukup, Lajos
Szentmiklóssy, Zoltán
Starting date 2007-07-01
Closing date 2011-07-31
Funding (in million HUF) 17.948
FTE (full time equivalent) 2.64
state closed project
Summary in Hungarian
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.
Summary
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.




 

Final report

  
Results in Hungarian
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.
Results in English
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.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=68262
Decision
Yes





 

List of publications

  
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, Gyenis Z,: Upward Morley's Theorem Downward, Math. Log. Quarterly, 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
Martinez JC; Soukup L: Universal locally compact scattered spaces, Topology Proc. 35 (2010), 19--36., 2010
Farkas B; Soukup L: More on cardinal invariants of analytic P-ideals, Comment. Math. Univ. Carolin. 50(2), volume 50, 281–295, 2009, 2009
Hajnal A; Komjáth P: Obligatory subsystems of triple systems, Acta Math. Hungar. 119 (2008), no. 1-2, 1--13., 2008
Hajnal A: Rainbow Ramsey Theorems for colorings establishing negative partition relations, Fund. Math. 198 (2008), no. 3, 255--262, 2008
Soukup L: Indestructible colourings and rainbow Ramsey theorems, Fund. Math. 202 (2009), no. 2, 161--180., 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



Back »