Abstract. Erdős, Lovász, and Spencer showed in the late 1970s that the dimension of the region of [Formula: see text]-vertex graph profiles, i.e., the region of feasible densities of [Formula: see text]-vertex graphs in large graphs, is equal to the number of nontrivial connected graphs with at most [Formula: see text] vertices. We determine the dimension of the region of [Formula: see text]-vertex tournament profiles. Our result, which explores an interesting connection to Lyndon words, yields that the dimension is much larger than just the number of strongly connected tournaments, which would be the answer expected as the analogy to the setting of graphs.

Research on the expander code shows that for a regular low-density parity-check (LDPC) code, the Tanner graph’s spectrum determines its properties, such as the minimum distance and the size of stopping sets. In this study, we demonstrate theoretically and experimentally that the performance of irregular LDPC codes is related to the graph spectrum. Our observations may provide an efficient metric to search for good irregular LDPC codes.

A k-graph H is called (p, μ)-dense if for all not necessarily disjoint sets A1, …, Ak ⊆ V(H) we have e(A1, …, Ak) ≥ p|A1| ⃛ |Ak| – μ|V(H)|k. This is believed to be the weakest form of quasi-randomness in k-graphs and also known as linear quasi-randomness. In this paper we show that for ℓ < k satisfying (k – ℓ) ∤ k, (p, μ)-denseness plus a minimum (ℓ + 1)-vertex-degree αnk–ℓ–1 guarantees Hamilton ℓ-cycles, but requiring a minimum ℓ-vertex-degree Ω(nk–ℓ) instead is not sufficient. This answers a question of Lenz–Mubayi–Mycroft and characterizes the triples (k, ℓ, d) such that degenerate choices of p and α force ℓ-Hamiltonicity. We actually prove a general result on ℓ-Hamiltonicity in quasi-random k-graphs, assuming a minimum vertex degree and essentially that every two ℓ-sets can be connected by a constant length ℓ-path. This result reduces the ℓ-Hamiltonicity problem to the study of the connection property. Moreover, we note that our proof can be turned into a deterministic polynomial-time algorithm that outputs the Hamilton ℓ-cycle. Our proof uses the lattice-based absorption method in the non-standard way and is the first one that embeds a nonlinear Hamilton cycle in linear quasi-random k-graphs.