This study presents a new type of cellular material that is simpler to make than conventional honeycombs and foams, while possessing many of the exceptional mechanical properties that make foams and honeycombs valuable as low density structural materials. The stochastic honeycombs had relative densities ranging from 7% to 13% with compressive strengths between 1 and 3MPa, and compressive stiffnesses between 60 and 130MPa. These values are comparable to those seen for commercial polypropylene honeycombs and significantly higher than those of commercial polypropylene foams. Rigid sandwich panels could be fabricated by reinforcing the stochastic honeycomb cores with external polypropylene face sheets. The panels could be assembled without adhesives, creating a rigid sandwich made entirely of a single material.