Summary: For a permutation $\sigma $ of length 3, we define the oriented graph $Q_{n}(\sigma )$. The graph $Q_{n}(\sigma )$ is obtained by imposing edge constraints on the classical oriented hypercube $Q_{n}$, such that each path going from $0^{n}$ to $1^{n}$ in $Q_{n}(\sigma )$ bijectively encodes a permutation of size $n$ avoiding the pattern $\sigma $. The orientation of the edges in $Q_{n}(\sigma )$ naturally induces an order relation ?$_{\sigma }$ among its nodes. First, we characterize ?$_{\sigma }$. Next, we study several enumerative statistics on $Q_{n}(\sigma )$, including the number of intervals, the number of intervals of fixed length $k$, and the number of paths (or permutations) intersecting a given node.

05A15

permutations avoiding patterns of length 3, edge-constrained hypercube, number of intervals, number of paths through a node, Catalan number