I am not the best person for a comprehensive answer but here are some blockchain-related combinatorics/graph theory problems I’ve seen in the past little while:
- light-client friendly shuffle: https://github.com/ethereum/eth2.0-specs/issues/563
- the plasma cash exit game is related to graph theory via Plasma Cash with smaller exit procedure, and a general approach to safety proofs
- Various designs for using RSA accumulators (https://ethresear.ch/t/rsa-accumulators-for-plasma-cash-history-reduction, Log(coins)-sized proofs of inclusion and exclusion for RSA accumulators)
- Alternative accumulator designs similar to ^
- Graph-theoretical algorithms needed for CBC e.g.: Beacon-chain friendly CBC Casper, Bitwise LMD GHOST
There are also math problems closer to cryptography e.g. I’m sure people are still on the lookout for more designs for VDFs or for SNARK/STARK-friendly hash functions, but I have less familiarity here.