If W is the simple random walk on the square lattice Z2, then W induces a random walk WG on any spanning subgraph G ⊂ Z2 of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, −x, y, −y}, the walk WG starts at the origin and follows the directions specified by W, only accepting steps of W along which the walk WG does not exit G. For any fixed G ⊂ Z2, the walk WG is distributed as the simple random walk on G, and hence WG is almost surely recurrent in the sense that WG visits every site reachable from the origin in G infinitely often. This fact naturally leads us to ask the following: does W almost surely have the property that WG is recurrent for every G ⊂ Z2? We answer this question negatively, demonstrating that exceptional subgraphs exist almost surely. In fact, we show more to be true: exceptional subgraphs continue to exist almost surely for a countable collection of independent simple random walks, but on the other hand, there are almost surely no exceptional subgraphs for a branching random walk.@en

Alon and Füredi (1993) showed that the number of hyperplanes required to cover {0,1}n∖{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}n while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open.@en

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.@en

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/d3) 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.@en

We continue the study by Melo and Winter (2019) [3] on the possible intersection sizes of a k-dimensional subspace with the vertices of the n-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than 2k−1 (the “large” sizes) are of the form 2k−1+2i. We show that this is almost true: the large intersection sizes are either of this form or of the form 35⋅2k−6. We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.@en

A subspace of F2n is called cyclically covering if every vector in F2n has a cyclic shift which is inside the subspace. Let h2(n) denote the largest possible codimension of a cyclically covering subspace of F2n. We show that h2(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 h2(ab) depending on h2(a) and h2(b) and extend some of our results to a more general set-up proposed by Cameron, Ellis and Raynaud.@en