Number Theory and its Interactions with Combinatorics  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
42750
Type K
Principal investigator T. Sós, Vera
Title in Hungarian Számelmélet és kombinatorikus vonatkozásai
Title in English Number Theory and its Interactions with Combinatorics
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Biró, András
Elekes, György
Ruzsa, Imre
Szemerédi, Endre
Starting date 2003-01-01
Closing date 2007-12-31
Funding (in million HUF) 10.675
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
A kutatók számos érdekes eredményt értek el a kombinatorikus számelmélet és geometria, gráfelmélet, diofantikus approximáció területén, itt csak néhányat említünk. Elekes és Ruzsa a Freiman, Balog-Szemerédi és Laczkovich-Ruzsa tételek közös általánosítását adják, ezzel a témakört egységesítik, és számos kombinatorikus geometriai tételt fejlesztenek tovább. Elekes Szabó E.-vel áttörést ért el a sok szabályosságot tartalmazó konfigurációk karakterizációjának általános problémájában, néhány korábbi eredményt jelentősen továbbfejlesztve. Szemerédi A. Khalfalah-val igazolja Sárközy, Roth és T. Sós azon sejtését, hogy: ha beosztjuk az egész számokat véges sok osztályba, akkor valamely osztályban van két olyan szám, amelyek összege négyzetszám, V. Vu-val közösen pedig Folkman egy sejtését bizonyítja. Biró javítja Ruzsa és Kolountzakis egész számok parkettázására vonatkozó eredményét. Erősíti és általánosítja a „karakterizáló sorozatok” témakör korábbi eredményeit. Ruzsa és B. Green meghatározzák tetszőleges véges kommutatív csoportban a legnagyobb összegmentes halmaz elemszámát. T. Sós Lovász L.-val megmutatja, hogy ha gráfok egy sorozatában a kis részgráfoknak ugyanaz az eloszlása, mint egy általánosított G véletlen gráfban, akkor ezen gráfoknak aszimptotikusan olyan struktúrája van, mint G-nek. T. Sós társszerzőkkel azt az alapkérdést vizsgálja, mikor van közel egymáshoz két gráf.
Results in English
The participants obtaind several interesting results in combinatorial number theory and geometry, graph theory, diophantine approximation, we list just a few of these results.. Elekes and Ruzsa give a common generalization of the Freiman, Balog-Szemerédi and Laczkovich-Ruzsa theorems, unifying in this way the subject and improving a lot of earlier results. Elekes with E. Szabó achieved a breakthrough in the general problem of characterizing configurations having a lot of reguarity, improving some earlier results. Szemerédi with A. Khalfalah proves the follwing conjecture of Sárközy, Roth and T. Sós: if we divide the set of integers into finitely many classes, then in one of the classes we can find two numbers such that their sum is a square, and with V. Vu he proves a conjecture of Folkman. Biró improves a result of Ruzsa and Kolountzakis on tilings of the integers, and, he proves generalizations and strengthenings of some results in the subject „characterizing sequences”.. Ruzsa and B. Green determine the size of the largest sumfree set in an arbitrary finite Abelian group. L. Lovász and T. Sós showed that generalized quasirandom sequences (whose subgraph densities match those of a fixed finite weighted graph) have a finite structure. T. Sós with co-authors defines the distance of two graphs that reflects the similarity , the closeness of both local and global properties.
Full text http://real.mtak.hu/778/
Decision
Yes





 

List of publications

  
Ruzsa Imre, T. Schoen, E. Croot: ARITHMETIC PROGRESSIONS IN SPARSE SUMSETS, Combinatorial Number Theory, de Gruyter, 2007, 157-164., 2007
T. Sós Vera, Simonovits Miklós: Quasirandom graphs and induced subgraphs, Combinatorics, Probability and Computing 12 (2003), 319-344., 2003
T. Sós Vera, Elek Gábor: Paradoxical decomposition and growth conditions, Combinatorics, Probability and Computing, 14 (1) 2005, 81-105., 2005
Elekes György, Ruzsa Imre: Few sums, many products, Studia Math. Hung. 40, (2003), 301-308., 2003
Elekes György: On the number of distinct radii of circles and parameters of other curves, Studia Math Hung. 40 (2003), 195-203., 2003
D. Abrego, Elekes György, S. Fernandez: Structural results for planar sets with many similar subsets, Combinatorica, 24 (4) 2004, 541-554., 2004
B. Csaba, A. Shokoufandeh Szemerédi Endre,: Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three, Combinatorica, 23 (2003), 35-72., 2003
G. Sárközy, S. Selkow, Szemerédi Endre: On the number of Hamiltonian cycles in Dirac graphs, Discrete Mathematics, 265 (2003), 237-250., 2003
Biró András: On the class number one problem for some special real quadratic fields, Proc. of the 2003 Nagoya Conference „On Yokoi-Chowla Conjecture and Related Problems”, Furukawa Total Pr. Co., 2004, 1-9, 2004
T. Sós Vera, Laczkovich Miklós: Analízis I., Nemzeti Tankönyvkiadó, 2005
T. Sós Vera, Simonovits Miklós: A hierarchy of randomness for graphs, Discrete Mathematics 303 (2005) 209-233., 2005
T. Sós Vera, M. Mubay: Explicit constructions of triple systems for Ramsey-Turán theory, Journal of Graph Theory 52 (2006)no. 3,211-216, 2006
T. Sós Vera, Ch. Borgs, J. Chayes, L. Lovasz, K. Vesztergombi: Counting graph homomorphisms, Algorithms and Combinatorics 36,J. Nesetril 60 (Springer) , 315-371., 2006
Szemerédi Endre, A. Rucinski, V. Rödl: A Dirac-type theorem for 3-uniform hypergraphs,, Combinatoricsrics, Probability and Computing, 15 (2006), no. 1-2., 229-251., 2006
Elekes György, Hegyvári N., Ruzsa I.: On difference sets in groups and generalized arithmetic progressions, benyújtva, 0
Elekes György, Tóth Csaba: Incidences of Not-too-degenerate Hyperplanes, Proceedings of the 21st annual symposium on computational geometry, 2005
Szemerédi Endre, A. Gyárfás, M. Ruszinkó, G. Sárközy: Three colour Ramsey numbers for paths, Combinatorica, 27 (1) 2007, 35-69., 2007
Szemerédi Endre, A. Gyárfás, M. Ruszinkó, G. Sárközy: An improved bound for the monochromatic cycle partition number, J. of Combinatorial Theory B, 96 (2006), no. 6., 855-873., 2006
Szemerédi Endre, V. Vu, B. Sudakov: On a problem of Erdos and Moser, Duke Math. Journal, 129 (2005), no1., 129-155., 2005
Biró András: Characterizations of groups generated by Kronecker sets, J. de Theorie des Nombres de Bordeaux, elfogadva, 2007
Szemerédi Endre, V. Vu: Long arithmetic progressions in sumsets and the number of x-sumfre sets, Proc. London Math. Soc, 90 (2005), 273-296., 2005
Szemerédi Endre, V. Vu: Long arithmetic progressions in sumsets: bounds and thresholds, elfogadva, J. of the A. M. S., 19 (2006), no.1., 119-169., 2006
T. Sós Vera, Ch. Borgs, J. Chayes, L. Lovasz, K. Vesztergombi: Convergent sequences of dense graphsI, Subgraph frequences, Metric proprties and Testing, benyújtva, 0
T. Sós Vera, Ch. Borgs, J. Chayes, L. Lovasz, K. Vesztergombi: Convergent sequences of dense graphs II, H-colorings, Statistical Phisics and Quotients, benyújtva, 0
T. Sós Vera, J. Balogh, B. Bollobás: The unlabelled speed of a hereditary graph property, benyújtva, 0
Ruzsa Imre: Additive and multiplicative Sidon sets, Acta Math. Hungar. 112 (2006), 345--354., 2006
Ruzsa Imre: Additive combinatorics and geometry of numbers, Proc. International Congress of Mathematicians, (Madrid 2006), ed. A. Laptev, European Math. Soc. 2006, 911--930.,, 2006
Ruzsa Imre, Keleti Tamás: Periodic decomposition of integer valued functions, Acta Math. Hung., to appear, 0
Szemerédi Endre, V. Vu: Finite and infinite arithmetic progressionsin Sumsets, Annals of Math. 163 (2006), 1-35., 2006
Szemerédi Endre, V. Vu, H. Nguyen: Subset sums in Zp, Proc. London Math. Soc., elfogadva, 0
Biró András: Interpolation by elliptic functions, Complex Variables and Elliptic Equations, elfogadva, 2008
Szemerédi Endre A. Rucinski, V. Rödl: A Dirac-type theorem for 3-uniform hypergraphs, Combinatorics, Probability and Computing, 15 (2006), no. 1-2., 229-251., 2006
Szemerédi Endre: An Old New Proof of Roth's Theorem, (Center de Recherches Mathematiques, CRM Proceedings and Lecture Notes, Volume 43, 2007, 51-54, 2007
K. Gyarmati, F.~Hennecart -Ruzsa Imre: Sums and differences of finite sets, Functiones et Approximatio, 37:175--186, 2007, 2007
K. Gyarmati, S.~Konyagin, Ruzsa. Imre: Double and triple sums modulo a prime, Additive Combinatorics, volume~43 of CRM Proceedings and Lecture Notes, pages 271--277, 2007
T. Sós Vera, Shiri Artstein-Avidan, Aviezri S. Fraenkel: A two parameter family of an extension of Beatty sequences, Discrete Math, megjelenés alatt, 2008
T. Sós Vera, Ch. Borgs, J. Chayes, L. Lovasz, K. Vesztergombi: Counting graph homomorphisms, Algorithms and Combinatorics 36,J. Nesetril 60 (Springer) , 315-371., 2006
T. Sós Vera, Lovász László: Generalized quasirandom graphs, J. Combin. Theory B 98 (2008), no.1, 146-163., 2008
Szemerédi Endre, A. Khalfalah: On the number of monochromatic solutions of $x+y=z\sp 2$., Combinatorics, Probability and Computing, 15 (2006), no. 1-2., 213-227., 2006
Ruzsa Imre, Ben Green: Sumfree sets in Abelian groups, Israel J. of Mathematics 147 (2005),157--188., 2005
Biró András: Strong characterizing sequences for subgroups of compact groups, J. of Number Theory, 121 (2) 2006, 324-354., 2006
Biró András: Divisibility of integer polynomials and tilings of the integers, Acta Arithmetica 118 (2) 2005, 117-127., 2005
Szemerédi Endre, V. Vu: Finite and infinite arithmetic progressionsin Sumsets, Annals of Math. 163 (2006), 1-35., 2006
Elekes György, Szabó Endre: How to find groups?, benyújtva, Combinatorica, 0
Elekes György, Ruzsa Imre: The structure of sets with few sums along a graph, J. of Combinatorial Theory A., 113 (7) 2006, 1476-1500., 2006
T. Sós Vera, Ch. Borgs, J. Chayes, L. Lovasz, B. Szegedy, K. Vesztergombi: Graph limits and parameter testing, STOC 2006, p.261-270, 2006



Back »