Theorem

My Erdös number is less or equal to 3.


Proof. The following list of publication was automatically generated by MathSciNet.

  • Kristiansen, Lars(N-OSLO); Schlage-Puchta, Jan-Christoph(B-GHNT); Weiermann, Andreas(B-GHNT) Streamlined subrecursive degree theory. Ann. Pure Appl. Logic 163 (2012), no. 6, 698--716.
  • Colbourn, C. J.(1-AZS-CEN); Kéri, G.(H-AOS-C); Soriano, P. P. Rivas; Schlage-Puchta, J.-C.(B-GHNT-PM) Covering and radius-covering arrays: constructions and classification. Discrete Appl. Math. 158 (2010), no. 11, 1158--1180.
  • Clark, Brent N.(3-WTRL-C); Colbourn, Charles J.(3-WTRL-C); Erdös, Paul(H-AOS) A conjecture on dominating cycles. Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985). Congr. Numer. 47 (1985), 189--197.

    Theorem

    My Erdös number is less or equal to 5.


    Proof. The following list of publication is collected from MathSciNet and Zentralblatt.

  • Kristiansen, L. and Niggl, K-H. On the computational complexity of imperative programming languages. Theoretical Computer Science, vol 318 (2004), 139-161.
  • Bellantoni, Stephen J.; Niggl, Karl-Heinz; Schwichtenberg, Helmut Higher type recursion, ramification and polynomial time. Ann. Pure Appl. Logic 104 (2000), no. 1-3, 17--30.
  • Bellantoni, Stephen; Pitassi, Toniann; Urquhart, Alasdair, Approximation and small-depth Frege proofs. SIAM J. Comput. 21 (1992), no. 6, 1161--1179.
  • Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael, On the complexity of unsatisfiability proofs for random $k$-CNF formulas. STOC '98, 561--571, ACM, New York, 1999.
  • Erdös, Paul; Saks, Michael; Sós, Vera T., Maximum induced trees in graphs. J. Combin. Theory Ser. B 41 (1986), no. 1, 61--79.

    It follows that the number is less or equal to 5.

    Alternative proof:
  • Kristiansen, L. and Jones, N.D. The flow of data and the complexity of algorithms. To appear in the proceedings from CiE'05, Cooper, Löwe, Torenvliet (eds.), Springer LNCS.
  • Peter Johansen, Neil Jones and Jens Clausen. A method for detecting structure in polyhedra. Pattern Recognition Letters Volume 2, Issue 4, Pages 217-225
  • Clausen, Jens; Krarup, Jakob. A family of bipartite cardinality matching problems solvable in $O(n\sp 2)$ time. Nord. J. Comput. 2, No.4, 496-501 (1995).
  • Harary, Frank; Krarup, J.; Schwenk, A. Graphs suppressible to an edge. Can. Math. Bull. 15, 201-204 (1972).
  • Chen, Hang; Schwenk, Allen J.; Erdös, Paul. Tournaments that share several common moments with their complements. Bull. Inst. Comb. Appl. 4, 65-89 (1992). QED

    The first proof is due to Benedikt Löwe. Please, inform me if you think the theorem can be strengthen or has an alternative proof.

    If you want to determine your own Erdös number, you might find this web site helpful.