Hypergraphs  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
48826
Type NK
Principal investigator Gyori, Ervin
Title in Hungarian Hipergráfok
Title in English Hypergraphs
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Elek, Gábor
Erdos, Péter
Katona, Gyula
Miklós, Dezso
Sali, Attila
Simonovits, Miklós
Simonyi, Gábor
Szemerédi, Endre
Tardos, Gábor
Starting date 2005-10-01
Closing date 2009-09-30
Funding (in million HUF) 21.840
FTE (full time equivalent) 11.71
state closed project





 

Final report

  
Results in Hungarian
A projekt célkitűzéseit sikerült megvalósítani. a négy év során több mint száz kiváló eredmény született, amiből eddig 84 dolgozat jelent meg a téma legkiválóbb folyóirataiban, mint Combinatorica, Journal of Combinatorial Theory, Journal of Graph Theory, Random Graphs and Structures, stb. Számos régóta fennálló sejtést bebizonyítottunk, egész régi nyitott problémát megoldottunk hipergráfokkal kapcsolatban illetve kapcsolódó területeken. A problémák némelyike sok éve, olykor több évtizede nyitott volt. Nem egy közvetlen kutatási eredmény, de szintén bizonyos értékmérő, hogy a résztvevők egyike a Norvég Királyi Akadémia tagja lett és elnyerte a Steele díjat.
Results in English
We managed to reach the goals of the project. We achieved more than one hundred excellent results, 84 of them appeared already in the most prestigious journals of the subject, like Combinatorica, Journal of Combinatorial Theory, Journal of Graph Theory, Random Graphs and Structures, etc. We proved several long standing conjectures, solved quite old open problems in the area of hypergraphs and related subjects. Some of the problems were open for many years, sometimes for decades. It is not a direct research result but kind of an evaluation too that a member of the team became a member of the Norvegian Royal Academy and won Steele Prize.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=48826
Decision
Yes





 

List of publications

  
A. Khalfalah, E. Szemerédi: On the number of monochromatic solutions of x+y=z2, COMBINATORICS PROBABILITY & COMPUTING; 15/1-2(2006), 213-227., 2006
J. Pach, R. Radoicic, G. Tardos, G. Tóth: Improving the crossing lemma by finding more crossings in sparse graphs, Discrete and Computational Geometry 36 (2006), 527-552., 2006
R. Anstee, B. Fleming, Z. Füredi, .A. Sali: Color critical hypergraphs and forbidden configurations, Discrete Math. and Theoretical Comput. Sci Proceedings http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/issue/archive, 2006
A. Sali , K.-D. Schewe: Counter-Free Keys and Functional Dependencies in Higher-Order Datamodels, Fundamenta Informaticae 70 (2006) 277-301, 2006
P.L. Erdős, P. Ligeti, P. Sziklai, D.C. Torney: Subwords in reverse complement order, to appear in Annals of Combinatorics 10 (4)(2006), ??--??., 2006
H. Aydinian, P.L. Erdős: All maximum size 2-part Sperner systems -in short, to appear in Comb. Prob. Comp. (2006), 1--4., 2006
J. Demetrovics, Gy. O.H. Katona, D. Miklós: On the security of individual data,, Annals of Mathematics and Artificial Intelligence 46(2006) 98-113, 2006
J. Demetrovics, Gy. O.H. Katona, D. Miklós, B. Thalheim,: On the number of independent functional dependencies, Foundations of Information and Knowledge Systems, Springer, LNCS 3861, 2006, pp.83-91., 2006
Gy. O.H. Katona, K. Tichler: Some contributions to the Minimum Representation Problem of Key Sytems, Foundations of Information and Knowledge Systems, Springer, LNCS 3861, 2006, pp.240-257., 2006
Füredi, Zoltán(1-IL); Pikhurko, Oleg(1-CMU); Simonovits, Miklós(H-AOS): 4-books of three pages. (English summary), J. Combin. Theory Ser. A 113 (2006), no. 5, 882--891., 2006
Haxell, P. E.(3-WTRL-B); \L uczak, T.(PL-POZN-DM); Peng, Y.(1-INS); Rödl, V.(1-EMRY-CS); Ruci\'nski, A.(PL-POZN-DM); Simonovits, M.(H-AOS); Skokan, J.(1-IL): The Ramsey number of hypergraph cycles. I. (English summary), J. Combin. Theory Ser. A 113 (2006), no. 1, 67--83., 2006
E. Gyori: Triangle-free hypergraphs, Comb. Prob. Comp. 15(2006) 185-191., 2006
P.Balister, E.Gyori, J. Lehel, R.Schelp: Connected graphs with no long paths, Discrete Math. 308 (2008) 4487-4494., 2008
P.Balister, E.Gyori, J.Lehel, R.Schelp: Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21 (2007) 237-250., 2007
T. Szabó, G. Tardos: Extremal problems for transversals in graphs with bounded degree, Combinatorica 26 (2006) (3), 333-351, 2006
A. Marcus, G. Tardos: Intersection reverse sequences and geometric applications, Journal of Combinatorial Theory Ser. A 113 (2006) (4) 675-691., 2006
J. Pach, G. Tardos: Forbidden paths and cycles in ordered graphs and matrices, Israel Journal of Mathematics 155 (2006), 359-372., 2006
G. Simonyi, G. Tardos: Local chromatic Number, Ky Fan's theorem, and circular colorings, Combinatorica 26 (2006), 587-626., 2006
I. Benjamini, G. Kozma, L. Lovász, D. Romik, G. Tardos: Waiting for a bat to fly by (in polynomial time), Combinatorics, Probability and Computing 15 (2006) (5), 673-683, 2006
N. Alon, I. Newman, A. Shen, G. Tardos, N. Vereshagin: Partitioning multidimensional sets in a small number of "uniform" parts, European J. of Combinatorics 28 (2006) (1), 134-144., 2006
J. Cooper, B. Doerr, J. Spencer, G. Tardos: Deterministic random walks, Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO'06), 185-197., 2006
G. Simonyi: Asymptotic values of the Hall-ratio for graph powers, Discrete Math., Volume 306, Issues 19--20, 2006, 2593--2601., 2006
G. Simonyi, G. Tardos: Colorful subgraphs in Kneser-like graphs, European J. Combin. 28 (2007) 2188-2200., 2007
N. Alon, I. Newman, A. Shen, G. Tardos, N. Vereshagin,: Partitioning multidimensional sets in a small number of "uniform'' parts,, European J. of Combinatorics 28, 2007
V. Rödl, A. Rucinski, E. Szemerédi: Perfect matchings in uniform hypergraphs with large minimum degree, EUROPEAN JOURNAL OF COMBINATORICS; 27/8(2006), 1333-1349., 2006
E. Szemerédi, V. Vu: Long arithmetic progressions in sumsets, thresholds and bounds, JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY; 19/1(2006), 119-169, 2006
J. Polcyn, V. Rödl, A. Rucinski, E. Szemerédi: Short paths in quasi-random triple systems with sparse underlying graphs, JOURNAL OF COMBINATORIAL THEORY SERIES B; 96/4(2006), 584-607., 2006
V. Rödl, A. Rucinski, E. Szemerédi: A dirac-type theorem for 3-uniform hypergraphs, COMBINATORICS PROBABILITY & COMPUTING; 15/1-2(2006), 229-251, 2006
E. Szemerédi, V. Vu: Finite and infinite arithmetic progressionsin sumsets, ANNALS OF MATHEMATICS; 163/2(2006), 1-35., 2006
G. Tardos, G. Tóth,: Decomposing multiple coverings with triangles,, Discrete and Computational Geometry, 38, 2007
J. Pach, G. Tardos, G. Tóth,: Indecomposable coverings, Discrete Geometry, Combinatorics and Graph Theory,, The China-Japan Joint Conference (CJCDGCGT 2005), Lecture Notes in Computer Science 4381,Springer,, 2007
Eyal Ackerman and Gábor Tardos,: On the maximum number of edges in quasi-planar graphs,, J. Combinatorial Theory, Ser. A. (JCT-A), 114, 2007
J. Cooper, B. Doerr, J. Spencer, G. Tardos,: Deterministic random walks on the integers,, European Journal of Combinatorics, 28, 2007
G. Simonyi, G. Tardos,: Colorfol subgraphs in Kneser-like graphs,, European Journal of Combinatorics, 28, 2007
X. Chen, J. Pach, M. Szegedy, G. Tardos,: Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles,, Symp. on Discrete Algorithms (SODA 2008), 2008
Jerrold.R. Griggs and Gyula O.H. Katona,: No four sets forming an N,, J. Combin. Theory, A 15 (2008) 677-685., 2008
Annalisa De Bonis and Gyula O.H. Katona,: Largest families without an r-fork,, Order, 24, 2007
Gyula O.H. Katona,: Forbidden inclusion patterns in the families of subsets (introducing a method),, to appear in Horizons of Combinatorics, Bolyai Studies, 2008
G. Simonyi, G. Tardos, S. Vrécica,: Local chromatic number and distinguishing the strength of topological obstructions,, Trans. Amer. Math. Soc., 361 (2009) 889-908., 2009
J. Körner, C. Malvenuto, G. Simonyi,: Graph-different permutations,, SIAM J. Discrete Math., to appear, 2008
J. Demetrovics, A. Sali,: Relational database design,, Algorithms of Informatics (Budapest, 2007, ed. A. Ivanyi), 849-881, 2007
J. Demetrovics, A. Sali,: Query rewriting in relations,, Algorithms of Informatics (Budapest, 2007, ed. A. Ivanyi), 882-930, 2007
G.O.H. Katona, A. Sali, K.-D. Schewe,: Codes that attain minimum distance in every possible direction,, Central European J. Math. 6 (2008) 1-11., 2008
H. Aydinian, P.L. Erdos,: All maximum size 2-part Sperner systems - in short,, Comb. Prob. Comp. 16(2007) 553-555., 2007
A. Apostolico, P.L. Erdos, M. Lewenstein,: Parameterized matching with mismatches,, J. Discrete Algorithms 5(2007) 135-140., 2007
P.L. Erdos,L. Soukup,: How to split antichains in infinite posets?,, Combinatorica 27(2007) 147-161., 2007
D. Duffus, P.L. Erdos, J. Nesetril, L. Soukup,: Splitting property in the graph homomorphism poset,, Comment Math. Univ. Carolinae 48(2007) 571-583., 2007
A. Gyarfas, M. Ruszinko, G.N. Sarkozy, E. Szemeredi,: Three-color Ramsey numbers for path,, Combinatorica 27(2007) 35-69., 2007
A. Sali, K-D. Schewe: Keys and Armstrong databases in trees with restructuring, Acta Cybernet. 18 (2008) 529-556., 2008
T. Luczak, M. Simonovits: On the minimum degree forcing F-free graphs to be (nearly) bipartite, Discrete Math. 308 (2008) 3998-4002., 2008
B. Bollobas, E. Gyori: Pentagons vs. triangles, Discrete Math. 308 (2008) 4332-4336., 2008
E. Gyori, M. Hornak, C. Palmer, M. Wozniak: Genal neighbour-distinguishing index of a graph, Discrete Math 308 (2008) 827-831, 2008
R. Martin, E. Szemerédi: Quadripartite version of Hajnal-Szemeredi theorem, Discrete Math. 308 (2008), 4337-4360., 2008
V. Rodl, A. Rucinski, E. Szemerédi: An approximate Dirac-type theorem for k-uniform hypergraphs, Combinatorica 28 (2008) 229-260., 2008
H.H. Nguyen, E. Szemerédi, V.H. Vu: Subset sums modulo a prime, Acta Arith. 131 (2008) 303-316., 2008
A. Gyarfas, M. Ruszinko, G.N. Sarkozy, E. Szemerédi,: Corrigendum: Three-color Ramsey number for paths, Combinatorica 28 (2008) 499-502, 2008
A. Gyarfas, G.N. Sarkozy, E. Szemerédi,: The Ramsey number of diamond-matchings and loose cycles in hypergraphs, Electron. J. Combin. 15 (2008) no 1, Research Paper 126, pp 14, 2008
N. Linial, J. Matousek, O. Sheffet, G. Tardos: Graph colouring with no large monochromatic component, COMBINATORICS PROBABILITY & COMPUTING; 17 (2008), 577-589., 2008
G. Simonyi: Necklace bisection with one cut less than needed, Electron J. Combin. 15 (2008) no 2., Note 16, 5 pp, 2008
K. Korner, C. Malvenuto, G. Simonyi: Graph-different permutations, SIAM J. Discrete Math. 22 (2008), 489-499., 2008
J. Demetrovics, G.O.H. Katona, D. Miklos: Functional dependencies distorted by errors, Discrete Appl. Math. 156 (2008), 862-869, 2008
L. Makar-Limanov, G.O.H. Katona: A problem for Abelian groups, Asian-Eur. J. Math. 1 (2008), 237-241., 2008
T. Carroll,, G.O.H. Katona: Bounds on maximal families of sets not containing three sets with A \cap B \subset C, A \nsubset B, Order 25 (2008), 229-236., 2008
D. Miklos: Subsums of a finite sum and extremal sets of vertices of the hypercube, Horizons of Combinatorics, 141-161, Bolyai Soc. Math. Stud. 17, Springer, 2008, 2008
E. Amiri, G. Tardos: High rate fingerprinting codes and the fingerprinting capacity, Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms 2009, 2009
G. Bogdanova, G.O.H. Katona: All q-ary equidistant 3-codes, J. of Combinatorics, Information and System Sciences; 34(2009) 161-167, 2009
G.O.H. Katona: Forbidden intersection patterns in the families of subsets, Proc. ICDM 2006; 165-174, 2009
Z. Füredi, A. Sali: Partition critical hypergraphs, Electronic Notes in Discrete Math. 34(2009) 573-577., 2009
A. Sali, K.-D. Schewe: A characterization of coincidence ideals for complex values, J.Universal Computer Science 15(2009) 304-354., 2009
J. Körner, G. Simonyi, B. Sinaimeri: On types of growth for graph-different permutations, J. Combinatorial Theory A; 116(2009) 713-723, 2009
G. Simonyi: Necklace splitting and the Tucker-Bacon theorem, Proc. 6th Japaneses-Hungarian Symp. on Discrete Math. and Its Applications, 348-350, 2009
P.L. Erdős, I. Miklós, Z. Toroczkai: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, Electronic J. Combinatorics 1-11., 2009
P.L. Erdős, L. Soukup: Quasi-kernels and Quasi-sinks in infinite graphs, Discrete Math. 309(2009) 3040-3048, 2009
P.L. Erdős, L. Soukup: No finite-infinite antichain duality in the homomorphism poset of directed graphs, Order (2009) 1-11, 2009
H. Kim, Z. Toroczkai, P.L. Erdős, I. Miklós, L.A. Székely: Degree-based graph construction, J. Phys. A: Math. Theor. 42(2009) 392001 (10 pp), 2009
G. Elekes, M. Simonovits, E. Szabó: A combinatorial distinction between unit circles and straight lines: how many coincidences can they have?, Combin. Probab. Comput. 18 (2009), 691--705., 2009
J. Balogh, B. Bollobás, M. Simonovits: The typical structure of graphs without given excluded subgraphs, Random Structures Algorithms 34 (2009), 305--318., 2009
G. Elek: L^2-spectral invariants and convergent sequences of finite graphs, J. Funct. Anal. 254 (2008), 2667--2689., 2008
G. Elek: Weak convergence of finite graphs, integrated density of states and a Cheeger type inequality, J. Combin. Theory Ser. B 98 (2008), 62--68., 2008
G. Elek: On limits of finite graphs, Combinatorica 27(2007), 503-507., 2007
A. Gyárfás, G. Sárközy, E. Szemerédi: Stability of the path---path Ramsey number, Discrete Math. 309 (2009), 4590--4595., 2009
V. Rödl, A. Ruciński, E. Szemerédi: Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116 (2009), 613--636, 2009
V. Rödl, A. Ruciński, M. Schacht, E. Szemerédi: A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Comment. Math. Univ. Carolin. 49 (2008), no. 4, 633--636, 2008
E. Győri, C. Palmer: A new type of edge-derived vertex coloring, Discrete Mathematics Volume 309(2009), 6344-6352, 2009




 

Events of the project

  
2009-06-03 09:41:41
Résztvevők változása



Back »