Professur Theoretische Informatik und Informationssicherheit

Publikationen

2014

  • H. Lefmann, D. Gunderson: Graphs on Affine and Linear Spaces and Deuber Sets
    2014, zur Publikation eingereicht
  • H. Lefmann: Extensions of the No-Three-In-Line Problem pdf
    2014, S. 1--12, zur Publikation eingereicht
  • H. Lefmann, C. Hoppen, Y. Kohayakawa: Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turan number
    2014, zur Publikation eingereicht

2013

  • H. Lefmann, Y. Person: Exact Results on the Number of Restricted Edge Colorings for some Families of Linear Hypergraphs
    Journal of Graph Theory 73, 2013, S. 1--31, ISBN/ISSN: 0364-9024, online first: DOI: 10.1002/jgt.21653
  • H. Lefmann, C. Hoppen, Y. Kohayakawa: An unstable hypergraph problem with a unique optimal solution
    Springer, 2013, S. 432-450, ISBN/ISSN: 978-3-642-36898-1, in: Information Theory, Combinatorics, and Search Theory: In Memory of
    Rudolf Ahlswede, H. Aydinian, F. Cicalese, and C. Deppe (Hrsg.): LNCS 7777.
  • H. Lefmann, C. Hoppen, K. Odermann: A colored version of the Erdős-Ko-Rado theorem for vector spaces pdf
    2013, Preprint

2012

  • H. Lefmann, C. Hoppen, Y. Kohayakawa: Hypergraphs With Many Kneser colorings pdf
    European Journal of Combinatorics 33, 2012, S. 816 - 843, doi: 10.1016/j.ejc.2011.09.025
  • H. Lefmann, C. Hoppen, Y. Kohayakawa: Edge colorings of graphs avoiding monochromatic matchings of a given size pdf
    Combinatorics, Probability & Computing 21, 2012, S. 203--218., doi: 10.1017/S0963548311000484

2011

  • H. Lefmann, C. Hoppen, Y. Kohayakawa: Edge colorings of graphs avoiding some fixed monochromatic subgraph with linear Turán number pdf
    Electronic Notes in Discrete Mathematic 38, 2011, S. 469-474, Proceedings 6th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2011).

2010

  • H. Lefmann, M. Schacht, Y. Person: A Structural Result for Hypergraphs With Many Restricted Edge Colorings pdf
    Journal of Combinatorics, 2010, S. 441-475, ISBN/ISSN: 2156-3527

2009

  • H. Lefmann, V. Rödl, M. Schacht, Y. Person: On Colorings of Hypergraphs Without Monochromatic Fano Planes pdf
    Combinatorics, Probability & Computing, volume 18, 2009, S. 803 - 818
  • H. Lefmann: Generalizations of Heilbronn's Triangle Problem
    European Journal of Combinatorics 30, 2009, S. 1686 - 1695, DOI 10.1016/j.ejc.2009.03.003
  • H. Lefmann, C. Hoppen, Y. Kohayakawa: Kneser Colorings in Uniform Hypergraphs pdf
    Electronic Notes in Discrete Mathematics 34, 2009, S. 219 - 223, DOI 10.1016/j.endm.2009.07.036
  • K. Plociennik: A Probabilistic PTAS for Shortest Common Superstring
    Proceedings "Mathematical Foundations of Computer Science 2009, 34th MFCS", 2009, S. 624-635, ISBN/ISSN: 978-3-642-03815-0, LNCS vol. 5734, Springer, Heidelberg

2008

  • H. Lefmann: Distributions of Points in the Unit-Square and Large k-Gons
    European Journal of Combinatorics 29 (4), 2008, S. 946 - 965
  • H. Lefmann: Distributions of Points in d Dimensions and Large k-Point Simplices pdf
    Discrete and Computational Geometry 40, 2008, S. 401 - 413
  • H. Lefmann: Point Sets in the Unit Square and Large Areas of Convex Hulls of Points pdf
    Journal of Combinatorial Optimization 16, 2008, S. 182 - 195, DOI: 10.1007/s10878-008-9168-7
  • H. Lefmann: No l Grid-Points in Spaces of Small Dimension
    Proceedings "4th International Conference on Algorithmic Aspects in Information and Management AAIM'08", Springer Verlag, LNCS 5034, 2008, S. 259-270, ISBN/ISSN: 978-3-540-68865-5, Hrsg. R. Fleischer und J. Xu
  • U. Tamm: Size of Downsets in the Pushing Order and a Problem of Berlekamp
    Discrete Applied Mathematics 156, no. 9, 2008, S. 1560 - 1566, ISSN: 0166-218X
  • K. Plociennik: Approximating Independent Set and Coloring in Random Uniform Hypergraphs
    Proceedings "Mathematical Foundations of Computer Science 2008, 33rd MFCS", 2008, S. 539-550, ISBN/ISSN: 978-3-540-85237-7, Springer Verlag, LNCS 5162, Hrsg. Edward Ochmanski und Jerzy Tyszkiewicz

2007

  • H. Lefmann: Generalizations of Heilbronn's Triangle Problem pdf
    Proceedings "4th European Conference on Combinatorics, Graph Theory and Applications EUROCOMB'07", Electronic Notes in Discrete Mathematics 29, 2007, S. 553 - 557, Elsevier
  • H. Lefmann: Point Sets in the Unit Square and Large Areas of Convex Hulls of Points pdf
    Proceedings "1st International Conference on Combinatorial Optimization and Applications COCOA'07", 2007, S. 230 - 241, Springer Verlag, LNCS 4616, Hrsg. A. Dress, Y. Xu and B. Zhu
  • H. Lefmann: Convex Hulls of Point-Sets and Non-uniform Uncrowded Hypergraphs pdf
    Proceedings "3rd International Conference on Algorithmic Aspects in Information and Management AAIM'07", 2007, S. 285 - 295, Springer Verlag, LNCS 4508

2006

  • H. Lefmann: Large Triangles in the d-Dimensional Unit-Cube  ps
    Theoretical Computer Science 363, 2006, S. 85 - 98
  • H. Lefmann: Distributions of Points and Large Convex Hulls of k Points pdf
    Proceedings "2nd International Conference on Algorithmic Aspects in Information and Management AAIM'06", 2006, S. 173 - 184, Springer Verlag, LNCS 4041, Hrsg. S.-W. Cheng and C.K. Poon

2005

  • U. Tamm: On perfect integer codes
    Proceedings 2005 International Symposium on Information Theory, Adelaide, Australien, IEEE, 09/2005, S. 117 - 120, DOI 10.1109/ITA.2007.4357607
  • H. Lefmann: Sparse Parity-Check Matrices over GF(q) pdf
    Combinatorics, Probability and Computing 14, 2005, S. 147 - 169
  • H. Lefmann: Distributions of Points in d Dimensions and Large k-Point Simplices  pdf
    Proceedings "11th Annual Computing and Combinatorics Conference COCOON'05", 2005, S. 514 - 523, Springer Verlag, LNCS 3595, Hrsg. L. Wang
  • H. Lefmann: Distributions of Points in the Unit-Square and Large k-Gons
    Proceedings "16th ACM-SIAM Symposium on Discrete Algorithms SODA'05", 2005, S. 241 - 250, ACM and SIAM
  • U. Tamm: Olinde Rodrigues and Combinatorics
    memorial volume "Mathematics and Social Utopias in France: Olinde Rodrigues and His Times: Mathematics and Social Utopia", History of Mathematics vol 28, AMS, 2005, S. 119 - 130, ISBN/ISSN: 978-0-8218-3860-0

2004

  • U. Tamm: Nonperfect shift codes
    Proceedings 4th European-Asian Workshop on Coding and Information Theory, Viareggio, Italien, 10/2004, S. 43 - 46, ISBN/ISSN: 3-9807929-5-1
  • U. Tamm, A. de la Cruz Nogueiras: Algorithms for hardware data compression
    Proceedings 4th European-Asian Workshop on Coding and Information Theory, Viareggio, Italien, 10/2004, S. 47 - 48, ISBN/ISSN: 3-9807929-5-1
  • U. Tamm: Compression and decompression algorithms
    Algorithms of Informatics, Chapter 10, Scolar Publisher, 09/2004, S. 421 - 463
  • H. Lefmann: Distributions of Points and Large Quadrangles pdf
    Proceedings "15th Annual Symposium on Algorithms and Computation ISAAC'04" , 2004, S. 657 - 668, Springer Verlag, LNCS 3341, Hrsg. R. Fleischer and G. Trippen
  • H. Lefmann: Large Triangles in the d-Dimensional Unit Cube pdf
    Proceedings "10th Annual International Computing and Combinatorics Conference COCOON'04", 2004, S. 43 - 52, Springer Verlag, LNCS 3106, Hrsg. K.Y. Chwa and J. I. Munro

2003

  • U. Tamm: On a problem of Berlekamp ps
    Proceedings 2003 International Symposium on Information Theory, Yokohama, Japan, 07/2003, S. 41
  • U. Tamm: Communication complexity and data compression pdf
    Proceedings 3rd Asian-European Workshop on Coding and Information Theory, Kamogawa, Japan, 06/2003, S. 92 - 95, ISBN/ISSN: 4-902087-04-9, invited contribution
  • U. Tamm: The Berlekamp-Massey algorithm and Combinatorics
    Proceedings International Workshop on Coding and Cryptography, WCC 2003, Versailles, (D. Augot, P. Charpin, and G. Kabatianski eds.), 2003, S. 433 - 443
  • H. Lefmann: On Heilbronn's Problem in Higher Dimension
    Combinatorica 23, 2003, S. 669 - 680
  • H. Lefmann: Sparse Parity Check-Matrices over Finite Fields ps
    Proceedings "9th International Computing and Combinatorics Conference COCOON'03", 2003, S. 112 - 121, Springer Verlag, LNCS 2697, Hrsg. T. Warnow and B. Zhu

2002

  • H. Lefmann, N. Schmitt: A Deterministic Polynomial Time Algorithm for Heilbronn's Triangle Problem in Dimension Three ps
    SIAM Journal on Computing 31, 2002, S. 1926-1947
  • U. Tamm: Orthogonal Polynomials in Information Theory
    2002, Habilitationsschrift
  • U. Tamm: Lattice paths not touching a given boundary
    Journal of Statistical Planning and Inference, 105(2), 2002, S. 433-448
  • H. Lefmann, N. Schmitt: A Deterministic Polynomial Time Algorithm for Heilbronn's Triangle Problem in Dimension Three pdf
    Proceedings "5th Latin American Symposium Theoretical Informatics LATIN'02", 2002, S. 165 - 180, Springer Verlag, LNCS 2286, Hrsg. S. Rajsbaum

2001

  • U. Tamm: Communication complexity and orthogonal polynomials
    Codes and Association Schemes (A. Barg and S. Litsyn eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 56, American Mathematical Society, 2001, S. 277-285
  • U. Tamm: Some aspects of Hankel matrices in Coding Theory and Combinatorics ps
    The Electronic Journal of Combinatorics, 8, #A1, 2001, S. 31 pp.

2000

  • U. Tamm: Communication complexity and association schemes
    Proceedings 2000 International Symposium on Information Theory, Sorrento, 06/2000, S. 4
  • H. Lefmann, H. Harborth: Coloring Arcs of Convex Sets
    Discrete Mathematics 220, 2000, S. 107-117
  • H. Lefmann, C. Bertram-Kretzberg: MODp-tests, Almost Independence and Small Probability Spaces
    Random Structures & Algorithms 16, 2000, S. 293-313
  • H. Lefmann, T. Hofmeister, C. Bertram-Kretzberg: An Algorithm for Heilbronn’s Problem
    SIAM Journal on Computing 30, 2000, S. 383-390
  • H. Lefmann: On Heilbronn’s Problem in Higher Dimension
    Proceedings ‘11th ACM-SIAM Symposium on Discrete Algorithms SODA’00’, ACM and SIAM, 2000, S. 60 - 64

1999

  • H. Lefmann, C. Bertram-Kretzberg: The Algorithmic Aspects of Uncrowded Hypergraphs
    SIAM Journal on Computing 29, 1999, S. 201-230
  • H. Lefmann, T. Hofmeister, C. Bertram-Kretzberg: Sparse 0,1-Matrices and Forbidden Hypergraphs
    Combinatorics, Probability and Computing 8, 1999, S. 417-427

1998

  • H. Lefmann, T. Hofmeister: On k-Partite Subgraphs
    Ars Combinatoria 50, 1998, S. 303-308
  • H. Lefmann, T. Hofmeister: Approximating Maximum Independent Sets in Uniform Hypergraphs
    Proceedings ‘Mathematical Foundations of Computer Science MFCS’98’, LNCS 1450, Hrsg. L. Brim, J. Gruska and J. Zlatuška, Springer Verlag, 1998, S. 562-570
  • H. Lefmann, T. Hofmeister, C. Bertram-Kretzberg: Sparse 0,1-Matrices and Forbidden Hypergraphs
    Proceedings "9th ACM-SIAM Symposium on Discrte Algorithms SODA'98", 1998, S. 181 - 187, ACM and SIAM

1997

  • H. Lefmann, P. Savický: Some Typical Properties of Large AND/OR Boolean Formulas
    Random Structures & Algorithms 10, 1997, S. 337-351
  • H. Lefmann, P. Savický, P. Pudlák: On Sparse Parity Check Matrices
    Designs, Codes and Cryptography 12, 1997, S. 107-130, Extended Abstract in: Proceedings ‘2nd Annual International Computing and Combinatorics
    Conference COCOON’96’, LNCS 1090, Hrsg. J.-Y. Cai und C. K. Wong, Springer Verlag, 1996, 41-49.
  • H. Lefmann, P. Fischer, K. Höffgen: PAC-Learning from General Examples
    Theoretical Computer Science 172, 1997, S. 43-65
  • H. Lefmann, C. Bertram-Kretzberg: MODp-tests, Almost Independence and Small Probability Spaces
    Proceedings "14th Annual Symposium on Theoretical Aspects of Computer Science STACS'97", 1997, S. 141 - 152, Springer Verlag, LNCS 1200, Hrsg. R. Reischuk and M. Morvan
  • H. Lefmann, C. Bertram-Kretzberg: The Algorithmic Aspects of Uncrowded Hypergraphs
    Proceedings "8th ACM-SIAM Symposium on Discrete Algorithms SODA'97", 1997, S. 296 - 304
  • H. Lefmann, T. Hofmeister, C. Bertram-Kretzberg: An Algorithm for Heilbronn's Problem
    Proceedings "3rd International Annual Computing and Combinatorics Conference COCOON'97", 1997, S. 23 - 31 , Springer Verlag LNCS 1276, Hrsg.
    T. Jiang and D.T Lee

1996

  • H. Lefmann, T. Hofmeister: Independent Sets in Graphs with Triangles
    Information Processing Letters 58, 1996, S. 207-210
  • H. Lefmann: Canonical Partition Relations for Ascending Families of Finite Sets
    Studia Scientiarum Mathematicarum Hungarica 31, 1996, S. 361-374
  • H. Lefmann, A. Bialostocki, T. Meerdink: On the Degree of Regularity of Some Equations
    Discrete Mathematics 150, 1996, S. 49-60
  • H. Lefmann, V. Rödl, B. Wysocka: Multicolored Subsets in Colored Hypergraphs
    Journal of Combinatorial Theory Ser. A 74, 1996, S. 209-248
  • H. Lefmann, T. Hofmeister: Computing Sparse Approximations Deterministically
    Linear Algebra and its Applications 240, 1996, S. 9-19
  • H. Lefmann, T. Hofmeister: A Combinatorial Design Approach to MAXCUT
    Random Structures & Algorithms 9, 1996, S. 163-175, Extended Abstract in: Proceedings 13th Annual Symposium on Theoretical Aspects of Computer Science STACS 96’, LNCS 1046, Hrsg. C. Puech und R. Reischuk, Springer Verlag, 1996, 441-452.
  • H. Lefmann, N. Hindman: Canonical Partition Relations for (m, p, c)-Systems
    Discrete Mathematics 162, 1996, S. 151-174
  • H. Lefmann, V. Rödl, B. Wysocka, C. Bertram-Kretzberg: Proper Bounded Edge-Colorings pdf
    Combinatorics, Complexity & Logic, Proceedings ‘1st International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS’96’, Hrsg. D. S. Bridges et al., Springer Verlag, 1996, S. 121-130, erweiterter Abstract

1995

  • H. Lefmann, A. Bialostocki, P. Erdös: Monochromatic and Zero-Sum Sets of Nondecreasing Diameter
    Discrete Mathematics 137, 1995, S. 19-34
  • H. Lefmann, V. Rödl, D. Duffus: Shift Graphs and Lower Bounds on Ramsey Numbers rk(l;r)
    Discrete Mathematics 137, 1995, S. 177-187
  • H. Lefmann, V. Rödl, R. Duke: On Uncrowded Hypergraphs
    Random Structures & Algorithms 6, 1995, S. 209-212
  • H. Lefmann, V. Rödl: On Erdös-Rado Numbers
    Combinatorica 15, 1995, S. 85-104
  • H. Lefmann, V. Rödl, R. Duke: A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
    SIAM Journal on Computing 24, 1995, S. 598-620
  • H. Lefmann, W. Deuber, N. Hindman, I. Leader: Infinite Partition Regular Matrices
    Combinatorica 15, 1995, S. 333-355
  • H. Lefmann, T. Thiele: Point Sets with Distinct Distances
    Combinatorica 15, 1995, S. 379-408
  • H. Lefmann, P. Savický: Some Typical Properties of Large AND/OR Boolean Formulas
    Proceedings "Mathematical Foundations of Computer Science MFCS'95", 1995, S. 237 - 246, Springer Verlag, LNCS 969, Hrsg. J. Wiedermann and P. Hájek
  • H. Lefmann, T. Hofmeister: Derandomization for Sparse Approximations and Independent Sets
    Proceedings "Mathematical Foundations of Computer Science MFCS'95", 1995, S. 201 - 210, Springer Verlag, LNCS, LNCS 969, Hrsg. J. Wiedermann and P. Hájek

1994

  • H. Lefmann, N. Alon, V. Rödl, R. Duke, R. Yuster: The Algorithmic Aspects of the Regularity Lemma
    Journal of Algorithms 16, 1994, S. 80-109
  • H. Lefmann, W. Deuber, N. Hindman, V. Bergelson: Rado’s Theorem for Commutative Rings
    Journal of Combinatorial Theory Ser. A 66, 1994, S. 68-92

1993

  • H. Lefmann: Ramsey Numbers for Monotone Paths and Cycles
    Ars Combinatoria 35, 1993, S. 271-279
  • H. Lefmann, V. Rödl: On Canonical Ramsey Numbers for Complete Graphs Versus Paths
    Journal of Combinatorial Theory Ser. B 58, 1993, S. 1-13
  • H. Lefmann, V. Rödl, K. Phelps: Rigid Linear Binary Codes
    Journal of Combinatorial Theory Ser. A 63, 1993, S. 110-128
  • H. Lefmann, H. Si Kaddour: On a Maximality Property of Partition Regular Systems of Equations
    Canadian Mathematical Bulletin 36, 1993, S. 96-102
  • H. Lefmann, V. Rödl, K. Phelps: Extremal Problems for Triple Systems
    Journal of Combinatorial Designs 1, 1993, S. 379-394
  • H. Lefmann, N. Hindman: Partition Regularity of (M, P,C)-Systems
    Journal of Combinatorial Theory Ser. A 64, 1993, S. 1-9
  • H. Lefmann: Ramsey Numbers for Monotone Paths and Cycles
    Ars Combinatoria 35, 1993, S. 271-279
  • H. Lefmann, V. Rödl: On Canonical Ramsey Numbers for Coloring Three-Element Sets
    Finite and Infinite Combinatorics in Sets and Logic, Hrsg. N. W. Sauer, R. E. Woodrow and B. Sands, Kluwer, 1993, S. 237-247
  • H. Lefmann, P. Fischer, K. Höffgen, T. Luczak: Approximations with Axis-Aligned Rectangles
    Proceedings ‘Fundamentals of Computation Theory FCT’93’, LNCS 710, Hrsg. Z. ´Esik, Springer Verlag, 1993, S. 244-255

1992

  • H. Lefmann, V. Rödl, R. Thomas: Monochromatic vs Multicolored Paths
    Graphs and Combinatorics 8, 1992, S. 323-332
  • H. Lefmann: Ramsey Numbers and Erdös Rado Numbers
    1992, Habilitationsschrift
  • H. Lefmann, N. Alon, V. Rödl, R. Duke, R. Yuster: The Algorithmic Aspects of the Regularity Lemma
    Proceedings "33rd IEEE Annual Symposium on Foundations of Computer Science FOCS'92", 1992, S. 473 - 481

1991

  • H. Lefmann: Non t-Intersecting Families of Linear Spaces over GF(q),
    Discrete Mathematics 89, 1991, S. 173-183
  • H. Lefmann: On Partition Regular Systems of Equations
    Journal of Combinatorial Theory Ser. A 58, 1991, S. 35-53
  • H. Lefmann, N. Alon, V. Rödl: On an Anti-Ramsey Type Result pdf
    Colloquia Mathematica Societatis János Bolyai, 60. Sets, Graphs and Numbers, 1991, S. 9-22

1990

  • H. Lefmann: On Families in Finite Lattices
    European Journal of Combinatorics 11, 1990, S. 165-179
  • H. Lefmann: Shadows, Density and Partitions
    Ars Combinatoria 29C, 1990, S. 140-156

1989

  • H. Lefmann: Canonical Partition Behaviour of Cantor Spaces
    Irregularities of Partitions, Hrsg. G. Halász und V. T. Sós, Springer Verlag, 1989, S. 93-105
  • H. Lefmann: A Note on Monoton Waves
    Journal of Combinatorial Theory Ser. A 50 , 1989, S. 316-318
  • H. Lefmann, W. Deuber: Partition Regular Systems of Homogeneous Linear Equations over Abelian Groups: The Canonical Case
    Combinatorial Mathematics, Annals of the New York Academy of Sciences 555, 1989, S. 167-170
  • H. Lefmann: An Extremal Problem for Graham-Rothschild Parameter Words
    Combinatorica 9, 1989, S. 153-160
  • H. Lefmann, B. Voigt: Partitions of Aω
    SIAM Journal on Discrete Mathematics 2, 1989, S. 524-529

1987

  • H. Lefmann: A Note on Ramsey Numbers
    Studia Scientiarum Mathematicarum Hungarica 22, 1987, S. 445-446
  • H. Lefmann: On Intersecting Families of Finite Affine and Linear Spaces Over GF(q)
    Colloquia Mathematica Societatis J´anos Bolyai, 52. Combinatorics, 1987, S. 365-374

1986

  • H. Lefmann: A Canonical Version for Partition Regular Systems of Linear Equations
    Journal of Combinatorial Theory Ser. A 41, 1986, S. 95-104

1985

  • H. Lefmann: Kanonische Partitionssätze
    1985, Dissertation

1984

  • H. Lefmann, B. Voigt: A Remark on Infinite Arithmetic Progressions
    Mathematics 52, 1984, S. 285-286

1982

  • H. Lefmann: Ramsey und Paris–Harrington Resultate in der Partitionstheorie
    1982, Diplomarbeit