Extremal combinatorics and its applications in other fields of mathematics  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
78439
Type NK
Principal investigator Gyori, Ervin
Title in Hungarian Extremális kombinatorika és alkalmazásai a matematika más területein
Title in English Extremal combinatorics and its applications in other fields of mathematics
Keywords in Hungarian kombinatorika, gráf, hipergráf, extremális struktúrák, regularitási lemma
Keywords in English Combinatorics, Graph, Hypergraph, Extremal structures, Regularity Lemma
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Combinatorial analysis
Panel Natural Sciences Committee Chairs
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Bárány, Imre
Elek, Gábor
Erdos, Péter
Gerbner, Dániel
Katona, Gyula
Katona, Gyula
Keszegh, Balázs
Ligeti, Péter
Miklós, Dezso
Miklós, István
Palmer, Cory
Pyber, László
Sali, Attila
Simonovits, Miklós
Simonyi, Gábor
Szemerédi, Endre
T. Sós, Vera
Tardos, Gábor
Starting date 2009-09-01
Closing date 2013-08-31
Funding (in million HUF) 29.856
FTE (full time equivalent) 23.26
state closed project
Summary in Hungarian
Az extremális a diszkrét matematika számos különböző területét foglalja magába, blokkrendszereket, extremális hipergráfokat, extremális halmazrendszereket, kapcsolódó kérdéseket részbenrendezett halmazokban, lineáris terekben, csoportokban. Az extrém gráfok vizsgálatát Turán kezdte a 40-es években, és az extrém gráfelmélet a kombinatorika központi témájává vált, különösen Magyarországon. A kutatások fontos kapcsolatokra derített fényt különböző gráfparaméterek között. Kiderült, hogy egyrészt algebra, valószínűségelmélet és geometria alapvetően alkalmazásra kerül az extrém struktúrák vizsgálatában, másrészt az extremális struktúrákat széles körben alkalmazzák a matematika más területein és egyéb diszciplinákban. A lista távolról sem teljes, de a projekt foglalkozni kiván az alkalmazásokkal és kapcsolatokkal csoportelméletben, információelméletben, gráfszínezésekben, geometriában, bioinformatikában, kódelméletben, játékelméletben és 01 mátrixokban is.
Summary
Extremal combinatorics involves many different areas of discrete mathematics, designs, extremal hypergraphs, extremal families of sets, related questions in posets, linear spaces, groups. The investigation of extremal graphs was initiated by Turán in the 40’s and extremal graph theory became a central subject of combinatorics, especially in Hungary. This research established essential relations between different graph parameters. It turned out that partly, algebra, probability theory and geometry is deeply involved in the study of extremal structures, partly, extremal structures are broadly applied in other fields of mathematics, or in other disciplines. The list is far not complete, but the project plans to deal with applications and connections in group theory, information theory, graph colourings, geometry, bioinformatics, coding theory, game theory, 01-matrices, as well.





 

Final report

 
Results in Hungarian
A projekt négy éve alatt 191 tudományos cikket írtunk és mintegy 250 előadást tartottunk ezekről nemzetközi konferenciákon. Ez csak ennek az OTKA projektnek a segítségével volt lehetséges. Mi szerveztük a EUROCOMB11-t, a legnagyobb európai kombinatorika konferenciát: a programbizottság elnöke és titkára a projekt vezetője ill. résztvevője volt éppúgy, mint a szervező bizottság elnöke és titkára. Nagyon fontos eredményeket értünk el gráfsorozatok limeszelméletében, régi extremális gráfelméleti sejtést bizonyítottunk fákról (a bizonyítás 160 oldal!). Mély és meglepő extremális hipergráfelméleti tételeket kaptunk körökről, partíció kritikus hipergráfokról. Kombinatorikán kívül, de kombinatorikus eszközökkel fontos Caratheodory típusú tételeket bizonyítottunk geometriában, megoldottuk Erdős régi problémáját számelméletben, karakterizáltuk a a pozitívan végesen generált provéges csoportokat vagy bioinformatikához illetve adatbázisokhoz kapcsolódó eredményeket láttunk be.
Results in English
We wrote 191 scientific papers during the four years of the project and gave about 250 lectures on them on international conferences. It was possible only with the support of this OTKA project. We organized EUROCOMB11, the biggest European combinatorial conference, the chairman and the secretary of the program committee and the organizing committee were the supervisor and a participant of this project. We achieved very important results in the theory of graph limits, proved old extremal graph theory conjectures on trees (the proof is 160 pages!). We got deep and surprising extremal hypergraph theorems on cycles, partition critical hypergraphs. Beyond combinatorics, but by means of combinatorial tools we proved important Caratheodory type theorems in geometry, solved old problems of Erdos in number theory, characterized the positively finitely generated profinite groups and proved theorems related to bioinformatics or data bases.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=78439
Decision
Yes





 

List of publications

 
J. Korner, S. Messuti, G. Simonyi: Families of graph-different Hamilton paths, SIAM J. Discrete Math., 26 (2012), 321-329, 2012
G. Simonyi, C. Tardif, A. Zsban: Colourful theorems and indices of homomorphism complexes, Electron. J. Combin., 20 (2013), no. 1, #P10., 2013
I. Barany, J-I. Ito, A. Vilcu, T. Zamfirescu: Every points is critical, Advances in Math., 235 (2013), 290-297, 2013
I. Barany, J-F. Marckert, M. Reitzner: Many empty triangles have a common edge, Discrete Comp. Geom., 50 (2013), 244-252, 2013
I. Barany, E. Roldan Pensado: A question from a famous paper of Erdos, Discrete Comp. Geom., 50 (2013), 253-261, 2013
I. Barany, F. Fodor, L. Montejano, D. Oliveros, A. Por: Colourful and fractional (p,q) theorems, Discrete Comp. Geom., accepted, 2013
Gabor Elek, Monod Nicolas: On the topological full group of a minimal Cantor Z2-system, Proc. Amer. Math. Soc. 141 (2013) no. 10 3549-3552, 2013
Gabor Elek: Connes Embbedings and von Neumann regular closures of amenable group algebras, Trans. Amer. Math. Soc. 365 (2013) no.6 3019-3039, 2013
Miklos Abert, Gabor Elek: Dynamical properties of profinite actions, Ergodic Dynamical Systems 32 (2012) no. 6. 1805-1835., 2012
Gabor Elek, Balazs Szegedy: A measure-theoretic approach to the theory of dense hypergraphs, Advances in Mathematics, 231 (2012) no 3-4 1731-1772, 2012
B. Keszegh , J. Pach, and D. Palvolgyi: Drawing planar graphs of bounded degree with few slopes, SIAM J. on Discrete Math , 27(2) (2013), 1171{1183., 2013
M. Henze, R. Jaume, B. Keszegh: On the complexity of the partial least-squares matching Voronoi diagram, EuroCG 2013 (2013), 193-196, 2013
B. Keszegh , N. Lemons, D. Palvolgyi:: Online and quasi-online colorings of wedges and intervals,, SOFSEM 2013: Theory and Practice of Computer Science, Lecture Notes in Computer Science 7741 (2013), 292-306, 2013
J. Pach, J. Solymosi, G. Tardos: Remarks on the Ramsey theory for trees, Combinatorica 32 (2012) (4), 473-482., 2012
G. Tardos: Construction of locally plane graphs with many edges, Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics series, 29 (J. Pach, ed.), Springer, 2012, 541-562, 2012
J. Pach, G. Tardos: Piercing quasi-rectangles-On a problem of Danzer and Rogers, Journal of Combinatorial Theory A 119 (2012) (7), 1391-1397., 2012
B. Mohar, G. Simonyi, G. Tardos: Local chromatic number of quadrangulations of surfaces, Combinatorica, to appear, 2013
Ian Levitt, Gábor N. Sárközy, Endre Szemerédi: How to avoid using the Regularity Lemma: Pósa's conjecture revisited, Discrete Mathematics 310(3): 630-641 (2010), 2010
Gábor N. Sárközy, Fei Song, Endre Szemerédi, Shubhendu Trivedi: A Practical Regularity Partitioning Algorithm and its Applications in Clustering, CoRR abs/1209.6540 (2012), 2012
Gyula O.H. Katona: Testing functional connection between two random variables, Prokhorov and Contemporary Probability Theory} (A.N. Shiryaev, S.R.S. Varadhan, E.L. Presman, editors) Springer, 2013, pp. 335-348, 2013
Gyula O.H. Katona: Sperner type theorems with excluded subposets, Discrete Appl. Math., 161(2013) 1251-1258, 2013
Gyula O.H. Katona: Constructing union-free pairs of k-element subsets, AKCE International J. Graphs and Combinatorics, 10(2013) 111-117, 2013
Gyula O.H. Katona and Krisztian Tichler: Encoding Databases Satisfying a Given Set of Dependencies,, FOiKS 2012, Kiel, Germany Thomas Lukasiewicz, Attila Sali, Edts. LNCS 7153, Springer, pp. 203-223, 2012
Gyula O.H. Katona and Zsolt Tuza: Color the cycles, Discrete Mathematics, 313(2013) 2026-2033, 2013
Peter Frankl, Mitsuo Kato, Gyula O.H. Katona and Norihide Tokushige: Two-coloring with many monochromatic cliques in both colors, J. Combin. Theory Ser B 103(2013) 415-427., 2013
Gyula O.H. Katona and Krisztian Tichler: Existence of a maximum balanced matching in the hypercube, Journal of Statistical Theory and Practice, accepted, 2013
A.E. Brouwer, A. Blokhuis and A. Sali: Note on the size of binary Armstrong codes, Designs, Codes and Cryptography, accepted, 2013
R.P. Anstee, C. Koch, M. Raggi and A. Sali: Forbidden Configurations and Product Constructions, Graphs and Combinatorics, to appear, 2013
R.P. Anstee, M. Raggi and A. Sali: Forbidden Configurations: Boundary cases, European J. Combin.35 2014, 51--66, 2014
Kohayakawa, Yoshiharu; Rödl, Vojtěch; Schacht, Mathias; Szemerédi, Endre: Sparse partition universal graphs for graphs of bounded degree, Adv. Math. 226 (2011), no. 6, 5041–5065., 2011
Gyárfás, András; Sárközy, Gábor N.; Szemerédi, Endre: Stability of the path-path Ramsey number, Discrete Math. 309 (2009), no. 13, 4590–4595., 2009
Ervin Győri, Gyula Y Katona, Nathan W Lemons: Hypergrpah Extensions of the Erdős-Gallai Theorem, Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013
P.L. Erdos - Z. Kiraly - I. Miklos: On the swap-distances of different realizations of a graphical degree sequence, Combinatorics, Probability and Computing 22 (2013), 366– 383, 2013
P.L. Erdos, Claude Tardif, Gabor Tardos: Regular languages and caterpil- lar duality, SIAM J. Disc. Math 27 (3) (2013), 1287–1294, 2013
A. Apostolico - P.L. Erdos - E. Gyori - Zs. Liptak - C. Pizzi: On the Periodic Subgraph Mining Problem, J. Discrete Algorithms 17 (2012), 24-30, 2012
Katona, G. Y., Sieben, N.: Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs, GRAPHS AND COMBINATORICS 29:(3) pp. 535-551., 2013
Miklós, I., Tannier, E.: Bayesian Sampling of Genomic Rearrangement Scenarios via Double Cut and Join Bioinformatics, Bioinformatics, 26(2010) 3012-3019., 2010
Erdõs, P., Miklós, I., Toroczkai, Z.: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, Elec. J. Combinatorics 17(1):R66, 2010
Kim, H., Toroczkai, Z., Erdõs, P., Miklós, I., Székely, L.: Degree-based graph construction, J. Phys. A., 42(39): 392001.1-392001.10., 2009
Miklós, I., Darling, A.: Efficient sampling of parsimonious inversion histories with application to genome rearrangement, Yersinia Genome Biology and Evolution, 1(1):153-164, 2009
G. Brightwell, G. Cohen, E. Fachini, M. Fairthorne, J. Körner, G. Simonyi, Á. Tóth: Permutation capacities of families of oriented infinite paths, SIAM J. Discrete Math., 24 (2010), 441--156., 2010
G. Elek, B. Szegedy: A measure-theoretic approach to the theory of dense hypergraphs., accepted, 2011
G. Simonyi, A. Zsbán: On topological relaxations of chromatic conjectures, European J. Combin., 31 (2010), 2110--2119, 2010
A. Gyárfás, G. Simonyi, Á. Tóth: Gallai colorings and domination in multipartite digraphs, J. Graph Theory, accepted, 2011
B. Mohar, G. Simonyi, G. Tardos: Local chromatic number of quadrangulations of surfaces, submitted, 2010
Elek Gabor, Lippner Gabor: Borel oracles and constant-time algorithms, Proc. of the AMS 138 (2010) 2939-2948., 2010
Elek Gabor, Lippner Gabor: Sofic equivalence relations, Journal of Functional Analysis 258 (2010) 1692-1708, 2010
Elek Gabor: Betti numbers are testable, Fete de combinatorics and computer science (2010) 139-150., 2010
Elek Gabor: Parameter testing for bounded degree graphs of subexponential growth, Random Structures and Algorithms (2010) 248-270., 2010
Abert Miklos, Elek Gabor: Dynamical properties of ergodic actions, to appear in Ergodic Theory and Dynamical Systems (2011), 2011
Elek Gabor: Connes Embeddings and von Neumann Regular Closures on Amenable Group Algebras, to appear in Transactions of the AMS, 2011
Balogh, József; Bollobás, Béla; Saks, Michael; Sós, Vera T.: The unlabelled speed of a hereditary graph property, J. Combin. Theory Ser. B 99 (2009), no. 1, 9--19., 2009
Galina Bogdanova, Gyula O.H. Katona: All $q$-ary equidistant 3-codes, J. of Combinatorics, Information and System Sciences 34 (2009) 161-167. (A Special Issue Dedicated to Ray-Chaudhury for his 75th birthday.), 2009
Gyula O.H. Katona: Finding at least one excellent element in two rounds, submitted for a volume, J. Statist. Planning Inference, 141(2011), 2946-2952., 2011
Gyula O.H. Katona, Keszler Anita and Attila Sali: On the Distance of Databases, Foundations of Information and Knowledge Systems (Proceedings of the 6th International Symposium, FoIKS 2010, Sofia, Bulgaria, February, 2010, Sebastian Link, Henri Prad, 2010
Chan, Tsz Ho; Győri, Ervin; Sárközy, András: On a problem of Erdős on integers, none of which divides the product of $k$k others., European J. Combin. 31 (2010), no. 1, 260–269., 2010
Győri, Ervin; Palmer, Cory: A new type of edge-derived vertex coloring., Discrete Math. 309 (2009), no. 22, 6344–6352., 2010
P.N. Balister, E. Gyori, R.H. Schelp: Coloring vertices and edges of a graph by nonempty subsets of a set, European J. Combin. 32 (2011), no. 4, 533--537., 2011
J. Balogh, B. Bollobas, M. Simonovits: The fine structure of octahedron-free graphs, J. Combin. Theory Ser. B 101 (2011), no. 2, 67--84, 2011
B. Csaba, A. Jamshed, E. Szemered: Embedding spanning trees, submitted to CPC, 2011
B. Csaba, I. Levitt, J. Nagy-Gyorgy, and E. Szemeredi: Tight bounds for embedding bounded degreee trees, Bolyai Society Mathematical Studies, X.(2010), Fete of Combinatorics, pp. 1-44., 2010
G. Elek: On the limit of large girth graph sequences, Combinatorica 30 (2010), no. 5, 553--563., 2010
G. Elek, G. Lippne: Borel oracles. An analytical approach to constant-time algorithms, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2939--2947., 2010
E. Flandrin, E. Gyori, H. Li, J. Shu: Cyclability in $k$-connected $K_{1,4}$-free graphs, Discrete Math. 310 (2010), no. 20, 2735--2741., 2010
A. Gyarfas, M. Ruszinko, G. Sarkozy, E. Szemeredi: Partitioning 3-colored complete graphs into three monochromatic cycles, Electron. J. Combin. 18 (2011), no. 1, Paper 53, 16 pp,, 2011
A. Gyarfas, G. Sarkozy, E. Szemeredi: Monochromatic matchings in the shadow graph of almost complete hypergraphs, Ann. Comb. 14 (2010), no. 2, 245--249., 2010
A. Gyarfas, G. Sarkozy, E. Szemeredi: Monochromatic Hamiltonian 3-tight Berge cycles in 2-colored 4-uniform hypergraphs, J. Graph Theory 63 (2010), no. 4, 288--299., 2010
A. Gyarfas, G. Sarkozy, E. Szemeredi: Long monochromatic Berge cycles in colored 4-uniform hypergraphs, Graphs Combin. 26 (2010), no. 1, 71--76., 2010
H. Kierstead, A.V. Kostochka, M. Mydlarz, E. Szemeredi, Endre: A fast algorithm for equitable coloring, Combinatorica 30 (2010), no. 2, 217--224., 2010
V. Rodl, A. Rucinski, E. Szemeredi: Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116 (2009), no. 3, 613--636., 2009
V. Rodl, A. Rucinski, E. Szemeredi: Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs, Advances in Mathematics, 227 (2011), no. 3, 1225--1299., 2011
S. Abbasi, I. Khan, G. Sarkozy, E. Szemeredi: A de-regularized proof of the El-Zahar Conjecture for Large Graphs, submitted to Journal of Combinatorial Theory B., 2011
G. Elek, E. Szabo: Sofic representations of amenable groups, to appear in the Proceedings of the AMS, 2011
M. Abert, G. Elek: Hyperfinite actions on countable sets and probability measure spaces, to appear in Contemporary Math, 2011
D. Gerbner, B. Keszegh, C. Palmer: Packing trees of different sizes into graphs, Discussiones Mathematicae Graph Theory, to appear, 2011
D. Gerbner, B. Keszegh: Path-search in a pyramid and in other graphs, Journal of Statistical Theory and Practice, to appear, 2011
B. Keszegh, D. Palvolgyi: Octants are Cover Decomposable, Discrete and Computational Geometry, accepted, 2011
B. Keszegh: Coloring half-planes and bottomless rectangles, Computational Geometry Theory and Applications, accepted, 2011
B. Keszegh: Box-respecting Colorings of n-dimensional Guillotine-Partitions, Discrete Mathematics, 311(8-9), (2011), 756-760., 2011
K. Arikushi, R. Fulek, B. Keszegh, F. Moric, Cs. D. Toth: Drawing Graphs with Orthogonal Crossings, Lecture Notes in Computer Science, 6410(2010), 135-146., 2010
B. Keszegh, J. Pach, D. Palvolgyi: Drawing planar graphs of bounded degree with few slopes, Lecture Notes in Computer Science, 6502(2011), 293-304, 2011
A. Szabo, A. Novak, I. Miklós, J. Hein: Reticular Alignment: A progressive corner-cutting method for multiple sequence alignment, BMC Bioinformatics*, 11(2010), 570., 2011
I. Somodi, I. Miklos, K. Virag: A Bayesian MCMC approach to reconstruct spatial vegetation dynamics from sparse vegetation maps, Landscape Ecology, 26(2010), 805-822, 2010
A. Sali, K.-D. Schewe: Weak functional dependencies on trees with restructuring, to appear in Acta Cybernetica., 2011
Z. Furedi, A. Sali: Partition critical hypergraphs, to appear in European J. Combin., 2011
A. Sali: Coding Theory Motivated by Relational Databases., LECTURE NOTES IN COMPUTER SCIENCE 6834(2011) 96-113., 2011
G.O.H. Katona and A. Sali: On the distance of databases, to appear in Annals of Mathematics and Artificial Intelligence, 2011
R.P. Anstee, M. Raggi and A. Sali: Evidence for a Forbidden Configuration Conjecture; one more case solved, submitted, 2011
R.P. Anstee, M. Raggi and A. Sal: Forbidden Configurations and Product Constructions, submitted, 2011
G.O.H. Katona: Testing functional connection between two random variables, accepted in the Prokhorov Festschrift., 2011
G.O.H. Katona: Sperner type theorems with excluded subposets, accepted in Discrete Appl. Math., 2011
G.O.H. Katona, G.Y. Katona and Z. Katona: Most probably intersecting families of subsets, accepted in Combinatorics, Probability, Computing., 2011
A.Jaikin-Zapirain, L.Pyber: Random generation of finite and profinite groups and group enumeration, Annals of Math. 173(2011)769-814, 2011
C.E.Praeger, L.Pyber,P.Spiga, E.Szabó: The Weiss conjecture for locally primitive graphs with automorphism groups admitting composition factors of bounded rank, Proc AMS, to appear, 2011
Csirmaz László, Ligeti Péter: LP problems in secret sharing, 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Kyoto, Japan (2011), 2011
I. Horváth, G.Y. Katona: Extremal P4-stable graphs, DISCRETE APPLIED MATHEMATICS, 159(2011) pp. 1786-1792., 2011
G.Y. Katona and N. Sieben: Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs, submitted to Graphs and Combinatorics, 2011
F. Cicalese, P.L. Erdos, Z. Liptak: Efficient Reconstruction of RC-Equivalent Strings over Arbitrary Paired Alphabets, to appear in J. Discrete Algorithms (2011), 1--26., 2011
E. Czabarka, P.L. Erdos, V. Johnson, A. Kupczok, L.A. Szekely: Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons, to appear in Moscow Journal of Combinatorics and Number Theory, 2011
E. Czabarka, P.L. Erdos, V. Johnson, V. Moulton: Generating Functions for Multi-labeled Trees, submitted, 2011
A. Aydinian, P.L. Erdos: On two-part Sperner systems for regular posets - Extended Abstract, in Proc. EUROCOMB'11, Electronic Notes in Discrete Mathematics ENDM1286 (2011), 2011
A. Apostolico, P.L. Erdos, I. Miklos, J. Siemons: Modulated String Searching, submitted to J. Disc. Alg., 2011
A. Apostolico, P.L. Erdos, E. Gyori, Z. Liptak, C. Pizzi: On the Periodic Subgraph Mining Problem, submitted, 2011
J. Pach, G. Tardos: Tight lower bounds for the size of epsilon-nets, Proc. 27th Annual SoCG, 2011
H. Johwari, M. Saglam, G. Tardos: Tight bounds for Lp samplers, finding duplicates, and related problems, Proceedings of the 30th Symposium on Principles of Database Systems, 2011
L. Csirmaz, G. Tardos: On-line secet sharing, Designs, Codes and Cryptography 63 (2012), 127-147., 2012
C.E.Praeger,L.Pyber,P.Spiga and E.Szabo: Graphs with automorphism groups admitting composition factors of bounded rank, Proc.AMS 140(2012).2307-2318, 2012
Z. Furedi, A. Sali: Partition critical hypergraphs, European Journal of Combinatorics 33 (2012) 844–852, 2012
Z. Furedi, A. Sali: Optimal multivalued shattering, SIAM J. DISCRETE MATH. Vol. 26, No. 2, pp. 737–744, 2012
R.P. Anstee, M. Raggi and A. Sali: Evidence for a Forbidden Configuration Conjecture; one more case solved, Discrete Mathematics 312 (2012) 2720–2729, 2012
P. Cheilaris, B. Keszegh, D. P´alv¨olgyi: Unique-maximum and conflict-free colorings for hypergraphs and tree graphs, SOFSEM 2012 Proceedings, 190–201, 2012
B. Keszegh, D. P´alv¨olgyi: Octants are Cover Decomposable, Discrete and Computational Geometry 47 (2012), 598–609., 2012
B. Keszegh: Coloring half-planes and bottomless rectangles, Computational Geometry Theory and Applications 45(2012), 495–507, 2012
D. Gerbner, B. Keszegh: Path-search in a pyramid and in other graphs, Journal of Statistical Theory and Practice, 6(2012), 303–314., 2012
D. Gerbner, B. Keszegh, C. Palmer: Generalizations of the Tree Packing Conjecture, Discussiones Mathematicae Graph Theory 32(2012), 569–582, 2012
K. Arikushi, R. Fulek, B. Keszegh, F. Mori´c, and Cs. D. T´oth:: Graphs that Admit Right Angle Crossing Drawings, Computational Geometry Theory and Applications 45 (2012), 169– 177., 2012
Gabor Elek: Finite graphs and amenability, Journal of Functional Analysis, 263, (2012) 2593-2612, 2012
Gabor Elek and Balazs Szegedy: A measure-theoretic approach of the thory of dense hypergraphs, Advances in Mathematics, 231 (2012) 1731-1772, 2012
Gyula O H Katona, Gyula Y Katona, Zsolt Katona: Most Probably Intersecting Families of Subsets, COMBINATORICS PROBABILITY & COMPUTING (ISSN: 0963-5483) 21: pp. 219-227., 2012
I. Barany, N. Enriquez: Jarnik's convex lattice polygon for non-symmetric norms, Math. Zeitschrift, 270(2012), 627--643, 2012
I. Barany, H. Maehara and N. Tokushige: Tetrahedra passing through a triangular hole, and tetrahedra fixed by a planar frame, Comp. Geom: Theory and Appl, 45(2012), 14-20, 2012
I. Barany: On a question of V. I. Arnold, Acta Math. Hung. 137(2012), 72-81., 2012
I. Barany, R. Karasev: Notes on the Caratheodory number, Discrete Comp. Geom., 48(2012), 783-792,, 2012
Miklós, I., Tannier, E.: Approximating the number of Double Cut-and-Join scenarios, Theoretical Computer Science 439 30-40, 2012
Miklós, I., Zádori, Z.: Positive Evolutionary Selection of an HD Motif on Alzheimer Precursor Protein Orthologues Suggests a Functional Role, PLoS Comp.Biol., 8(2): e1002356., 2012
P.L. Erd˝os, D. Gerbner, D. Mubayi, N. Lemons, C. Palmer, B. Patk´os: Two-part set systems, Elec. J. Combinatorics 19 (2012), 1–10., 2012
E. Czabarka - P.L. Erd˝os - V. Johnson - A. Kupczok - L.A. Sz´ekely: Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons, Moscow Journal of Combinatorics and Number Theory 1 (2011), 220–232., 2011
A. Gyarfas, G. Simonyi, A. Toth: Gallai colorings and domination in multipartite digraphs, J. Graph Theory, 71(2012),278--292., 2012
E. Gyori, N. Lemons: Hypergraphs with no cycles of length 4, Discrete Math., 312(2012), 1518-1520., 2012
E. Gyori, H. li: A note on the number of triangles in $C_{2k+1}$-free graphs, Comb. Prob. Comp., 21(2012), 187-191., 2012
E. Gy ori, N. Lemons: 3-uniform hypergraphs avoiding a given odd cycle, Combinatorica, 32(2012), 187-203, 2012
E. Gyori, N. Lemons: Hypergraphs with no cycle of a given length, Comb. Prob. Comp., 21(2012), 193-201., 2012
T. Luczak, M. Simonovits, J. Skokan: On the Multi-coloured Ramsey Numbers of Cycles, Journal of Graph Theory 69(2012), 169–175, 2012
Marcin Anholcera, Cory Palmer: Irregular labelings of circulant graphs, Discrete Mathematics 312(2012), 3461–3466, 2012
C.Borgs, J.T.Chayes, L.Lovasz, V.T.Sos, K.Vesztergombi: Convergent sequences of dense graphs II,Multiway cuts and statistical physics, Annals of mathematics, 2012
B. Lidicky, H. Liu, C. Palmer: On the Turan number of forests, Electronic Journal of Combinatorics, 20 (2013) 13, 2013
A. Ferber, R. Glebov, M. Krivelevich, H. Liu, C. Palmer, T. Valla, M. Vizer: The biased odd cycle game, Electronic Journal of Combinatorics, 20(2013) pg. 10, 2013
D. Gerbner, B. Keszegh, N. Lemons, D. Palvolgyi, C. Palmer, B. Patkos: Saturating Sperner families, Graphs and Combinatorics, 29 (2013) 1355-1364, 2013
D. Gerbner, N. Lemons, C. Palmer, B. Patkos, D. Palvolgyi, V. Szecsi: Almost cross-intersecting and almost cross-Sperner pairs of families of sets, Graphs and Combinatorics, 29 (2013) 489-498, 2013
D. Gerbner, N. Lemons, C. Palmer, B. Patkos, V. Szecsi: Almost intersecting families of sets, SIAM Journal on Discrete Mathematics, 26 (2012) 1657-1669, 2012
M. Anholcer, C. Palmer: Irregular labellings of circulant graphs, Discrete Math., 312 (2012) 3461-3466, 2012
D. Gerbner, B. Keszegh, C. Palmer: Generalizations of the tree packing conjecture, Discussiones Mathematicae Graph Theory, 32 (2012) 569-582, 2012
D. Gerbner, G.O.H. Katona, D. Pálvölgyi, B. Patkós: Majority and Plurality Problems, Discrete Applied Mathematics 161 (2013) 813-818, 2013
Miklós, I., Erdős, P., Soukup, L.: Towards random uniform sampling of bipartite graphs with given degree sequence, Electronic Journal of Combinatorics 20(1):P16, 2013
Miklós, I., Tannier, E.: Approximating the number of Double Cut-and-Join scenarios, Theoretical Computer Science 439:30-40, 2012
N.Gill,L.Pyber,I.Short,E.Szabo: On the product decomposition conjecture for finite simple groups, Groups ,Geometry and Dynamics accepted, 2013
I. Bárány, M. Reitzner: Poisson polytopes, Annals Prob., 38 (2010), 1507—1531, 2010
I. Bárány, M. Reitzner: The variance of random polytopes, Advances in Math., 225 (2010), 1986-2001, 2010
I. Bárány, J-I, Ito, A. Vilcu, T. Zamfirescu: Every points is critical, submitted, 2009
I. Bárány, F Fodor, V. Vigh: Intrinsic volumes of inscribed random polytopes in smooth convex bodies, Annals of Appl. Prob.,to appear (2010), 2010
I. Bárány, N. Enriquez: Jarnik's convex lattice polygon for non-symmetric norms, submitted, 2010
I. Bárány, P. Blagojevic and A. Dmitrijevic Blagojevc: Functions, measures, and equipartitioning convex $k$-fans, submitted, 2010
I. Bárány, W Steiger: On the variance of random polygons, submitted, 2010
Ervin Gyõri, Gyula Y Katona, Nathan Lemmons: Hypergraph Extensions of the Erdõs-Gallai Theorem. (extended abstract), ELECTRONIC NOTES IN DISCRETE MATHEMATICS 36: pp. 655-662. (2010), 2010
Dudek, Aneta, ¯ak, Andrzej, Katona Gyula Y: Hamilton-chain saturated hypergraphs., DISCRETE MATHEMATICS 310:(6-7) pp. 1172-1176. (2010), 2010
Zahoranszky LA, Katona GY, Hari P, Malnasi-Csizmadia A, Zweig KA, Zahoranszky-Kohalmi G: Breaking the hierarchy - a new cluster selection mechanism for hierarchical clustering methods., ALGORITHMS FOR MOLECULAR BIOLOGY 4: pp. 1-22. Paper 12. (2009), 2009
Mikio Kano, Gyula Y Katona, Jácint Szabó: Elementary Graphs with Respect to f-Parity Factors., GRAPHS AND COMBINATORICS 25:(5) pp. 717-726. (2009), 2009
J. Pach, G. Tardos: Conflict-free colorings of graphs and hypergraphs, Combinatorics, Probability and Computing 18 (2009), 819-834., 2009
J. Pach, J. Solymosi, G. Tardos: Crossing numbers of imbalanced graphs, Journal of Graph Theory 64 (2010) (1), 12-21, 2010
J. Pach, G. Tardos: Coloring axis parallel rectangles, Journal of Combinatorial Theory, Ser. A 117 (2010), 776-782., 2010
R. Moser, G. Tardos: A constructive proof of the general Lovász Local Lemma, Journal of the ACM 57 (2010) (2) Art. 11, 15pp., 2010
G. Simonyi, G. Tardos: On directed local chromatic number, shift graphs, and Borshuk-like graphs, J. Graph Theory, 66 (2011), 65-82, 2011
H. Gebauer, T. Szabo, G. Tardos: The local lemma is tight for SAT, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), to appear., 2011
R. Anstee, F. Barekat, and A. Sali: Small Forbidden Configurations V: Exact bounds for $4\times 2$ cases, Studia Sci. Math. Hun., 48(2011) 1-22., 2011
Zoltán Füredi and A. Sali: Partition critical hypergraphs, ELECTRONIC NOTES IN DISCRETE MATHEMATICS 34, 573-577. (2009), 2009
Zoltán Füredi and A. Sali: Some New Bounds on Partition Critical Hypergraphs, submitted to European J. Combin., 2010
G.O.H. Katona, A. Keszler, A. Sali: On the Distance of Databases, Lecture Notes in Comput. Sci., 5956, (2010), 76-93., 2010
Hyunju 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 (10pp, 2009
P.L. Erdős - I. Miklós - Z. Toroczkai: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, Elec. J. Combinatorics 17 (1) (2010), R66 (10pp)., 2010
P.L. Erdős - L. Soukup: No finite-infinite antichain duality in the homomorphism poset of directed graphs, Order (2010), 1--11. doi:10.1007/s11083-009-9118-8., 2010
P.L. Erdős - L. Soukup - J. Stoye: Balanced vertices in trees and a simpler algorithm to compute the genomic distance, Appl. Math. Letters 24 (1) (2011), 82--86., 2011
F. Cicalese - P.L. Erdős - Zs. Lipták: Efficient Reconstruction of RC-Equivalent Strings, Proc. 21st International Workshop on Combinatorial Algorithms, IWOCA 2010 (2010), 1--17., 2010
A. Apostolico - P.L. Erdős - A. Jüttner: Parameterized Searching with Mismatches for Run-length Encoded Strings, to appear in Proc. of SPIRE 2010 (2010), 1--11., 2010
H. Aydinian - É. Czabarka - K. Engel - P.L. Erdős - L.A. Székely: A note on full transversals and mixed orthogonal arrays, Australian J. Combinatorics 48 (2010), 133—141, 2010
H. Aydinian - É. Czabarka - K. Engel - P.L. Erdős - L.A. Székely: A tour of $M$-part $L$-Sperner families, in press, J.Comb. Theory (A), 118(2011), 702-725., 2011
N.Nikolov,L.Pyber: Product decompositions of quasirandom groups and a Jordan type theorem, J.Eur Math.Soc.13(4) (2011)1063-1077, 2011
Csirmaz Laszlo, Ligeti Peter, Tardos Gabor: On infinite secret sharing schemes, xxx, 2011
B. Keszegh, J. Pach, D. Pálvölgyi, and G. Tóth: Graph Drawing 2008, Journal of Graph Algorithms and Applications 14(1), (2010), 5--17., 2010
B. Keszegh, J. Pach, D. Pálvölgyi: Drawing planar graphs of bounded degree with few slopes, Graph Drawing 2010, 2010
D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, B. Patkós and D. Pálvölgyi: Polychromatic colorings of arbitrary rectangular partitions, 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (2009); Discrete Mathematics, 310(1), Elsevier (2010), 21--30., 2010
R. Fulek, B. Keszegh, F. Moric, I. Uljarevic,: On Polygons Excluding Point Sets, The 22nd Canadian Conference on Computational Geometry (CCCG10) Proceedings (2010), 273--27, 2010
P. Cheilaris, B. Keszegh, D. Pálvölgyi: Unique-maximum and conflict-free colorings for hypergraphs and tree graphs, http://arxiv.org/abs/1002.4210, 2010
D. Gerbner, B. Keszegh, C. Palmer: Generalizations of the Tree Packing Conjecture, 8th French Combinatorial Conference, Paris (2010), 2010
K. Arikushi, R. Fulek, B. Keszegh, F. Moric and Cs. D. Tóth: Drawing Graphs with Orthogonal Crossings, 36th International Workshop on Graph Theoretic Concepts in Computer Science, Zarós (2010), 2010
D. Gerbner, B. Keszegh, D. Pálvölgyi and G. Wiener: Search with density tests, Coimbra Meeting on 0-1 Matrix Theory and Related, Coimbra (2010), 2010
D. Gerbner, N. Lemons, C. Palmer, B. Patkós, V. Szécsi: Cross-Sperner families, Studia Sci. Math. Hungarica (accepted) (2010), 2010
D. Gerbner, N. Lemons, C. Palmer, B. Patkós, V. Szécsi: Almost intersecting families of sets, submitted (2010), 2010
D. Gerbner, B. Keszegh, C. Palmer: Generalizations of the tree packing conjecture, submitted (2010), 2010
D. Gerbner, B. Keszegh, C. Palmer, B. Patkós, V. Szécsi: Almost crossintersecting and almost cross-Sperner pairs of families of sets, submitted (2010), 2010
Gerbner Dániel, Pálvölgyi Dömötör, Patkós Balázs, Wiener Gábor: Finding the maximum and minimum elements with one lie, Discrete Applied Mathematics, 158 (2010), no. 9, 988--995., 2010
Gerbner Dániel: The Magnus-Derek game in groups, xxx, 2010





 

Events of the project

 
2010-08-12 10:17:07
Résztvevők változása
2010-06-22 13:17:54
Résztvevők változása




Back »