Given an integer n, let G(n) be the number of integer sequences n − 1 ≥ d₁ ≥ d₂ ≥ · · · ≥ d_n ≥ 0 that are the degree sequence of some graph. We show that G(n) = (c + o(1))4ⁿ/n³/⁴ for some constant c > 0, improving both the previously best upper and lower bounds by a factor of n¹/⁴ (up to polylog-factors). Additionally, we answer a question of Royle, extend the values of n for which G(n) is known exactly from n ≤ 290 to n ≤ 1651 and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative.

Given a finite poset P, we say that a family F of subsets of [n] is P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The induced saturation number of P, denoted by sat^∗(n,P), is the size of the smallest P-saturated family with ground set [n]. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that sat^∗(n,P)=O(n^c), where c≤|P|²/4+1 is a constant depending on P only. We obtain this result by bounding the VC-dimension of our family.

Two permutations σ and π are ℓ-similar if they can be decomposed into subpermutations σ(1), . . . ,σ(ℓ) and π(1), . . . ,π(ℓ) such that σ(i) is order-isomorphic to π(i) for all i ∈[ℓ]. Recently, Dudek, Grytczuk, and Ruciński Variations on twins in permutations, Electron. J. Combin., 28 (2021), P3.19. posed the problem of determining the minimum ℓ for which two permutations chosen independently and uniformly at random are ℓ-similar. We show that two such permutations are O(n1/3 log11/6(n))-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalizes to simultaneous decompositions of multiple permutations.

The deck of a graph G is the multiset of cards {G−v:v∈V(G)}. Myrvold (1992) showed that the degree sequence of a graph on n≥7 vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree d can be reconstructed from any deck missing O(n/d³) cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.

A subspace of F₂ⁿ is called cyclically covering if every vector in F₂ⁿ has a cyclic shift which is inside the subspace. Let h₂(n) denote the largest possible codimension of a cyclically covering subspace of F₂ⁿ. We show that h₂(p)=2 for every prime p such that 2 is a primitive root modulo p, which, assuming Artin's conjecture, answers a question of Peter Cameron from 1991. We also prove various bounds on h₂(ab) depending on h₂(a) and h₂(b) and extend some of our results to a more general set-up proposed by Cameron, Ellis and Raynaud.

Alon and Füredi (1993) showed that the number of hyperplanes required to cover {0,1}ⁿ∖{0} without covering 0 is n. We initiate the study of such exact hyperplane covers of the hypercube for other subsets of the hypercube. In particular, we provide exact solutions for covering {0,1}ⁿ while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open.