[rurban]

As I already commented in the first submission of this article:

Now that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh.

This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements with Unicode. switch in C is only efficient for dense tables, but not sparse. sparse tables are linear, but could be constant. A switch in Pascal was constant, but so far GCC and llvm didn't care. gperf neither.

see http://ilan.schnell-web.net/prog/perfect-hash/algo.html and http://programming.sirrida.de/hashing.html#c_case_of_string

[nsane]

Isn't the proof for Hamiltonian cycles? From what I could understand from your link to CHM92, it only requires a cyclic graph to stop, which isn't necessarily supposed to touch all vertices. Is that right?

[jonnycomputer]

The Hamiltonian cycle is only a motivating example. The conjecture which was proven is much more general.

https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-p...

[less_less]

Huh, I was thinking the same thing about a related problem: compressed static maps by solving sparse matrices: https://docs.rs/compressed_map/0.1.0/compressed_map/

To get a concrete bound though, you'd probably need to know what is K.