University of Louisville Logo

24th Cumberland Conference on Combinatorics, Graph Theory, and Computing

From the irregularity strength of graphs to the degree irregularity of random hypergraphs

Jenő Lehel

As everyone knows, there is no simple graph with all distinct vertex degrees. But do there exist simple $3$-uniform hypergraphs with that property? Since they do, one might ask what is the probability that a random $r$-uniform hypergraph has no two vertices of the same degree? Does this probability approach $1$ or $0$, as the number of vertices approaches infinity?

An overview will be given starting with the very first degree irregularity questions and results due Gary Chartrand, Michael Jacobson, the late Dick Schelp, and many others, and leading to the most recent results on repeated degrees in random uniform hypergraphs obtained by Paul Balister, Michal Morayne, et al.

Slides (PDF)