Displaying 621 – 640 of 771

Showing per page

Une variante de la méthode isopérimétrique de Hamidoune, appliquée au théorème de Kneser

Éric Balandraud (2008)

Annales de l’institut Fourier

En théorie additive des nombres, le théorème de Kneser joue aujourd’hui un rôle central dans un grand nombre de démonstrations. Hamidoune a récemment développé une approche alternative au théorème de Kneser, qu’il a appelé méthode isopérimétrique et qui lui a permis de donner de nouvelles preuves et de nombreuses généralisations de résultats classiques. Cependant, jusqu’à maintenant, on ne connaissait pas de démonstration du théorème de Kneser par cette méthode. Nous proposons ici une nouvelle approche...

Uniform distribution modulo one and binary search trees

Michel Dekking, Peter Van der Wal (2002)

Journal de théorie des nombres de Bordeaux

Any sequence x = ( x k ) k = 1 of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let H n ( x ) be the height of the tree generated by x 1 , , x n . Obviously log n log 2 - 1 H n ( x ) n - 1 . If the sequences x are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists c > 0 such that H n ( x ) c log n as n for almost all sequences x . Recently...

Currently displaying 621 – 640 of 771