Two trees multiplied together stay just as hard to avoid

Take a tree, the branching kind mathematicians draw with dots and lines and no closed loops. Take a second tree. Now multiply them, in the sense combinatorialists mean by a Cartesian product: lay out a grid where every point of the first tree meets every point of the second, and connect two grid points whenever they agree in one coordinate and are neighbors in the other. The result is a lattice-like graph, more tangled than either parent. A question that has resisted answers for decades: how many connections can a large network hold before it is forced to contain a copy of that pattern?

Lanchao Wang and Caihong Yang say the answer is the same order of magnitude no matter which two trees you started with. Their preprint, posted to arXiv on 30 July 2026, proves a conjecture made by Matěj Bradač, Oliver Janzer, Benny Sudakov and István Tomon, who had settled the case where one of the two factors is a simple path.

The quantity in question is the Turán number, written ex(n, H). Fix a pattern graph H. Then ex(n, H) is the largest number of edges a graph on n vertices can have while still containing no copy of H at all. For patterns with an odd cycle in them, the answer has been understood since the 1940s. For bipartite patterns, the ones whose vertices split into two groups with every edge crossing between them, the problem is famously stubborn, and a conjecture of Paul Erdős about which exponent should appear has driven a great deal of the work in the area.

Bradač, Janzer, Sudakov and Tomon proved that when you take any nontrivial tree T and any nontrivial path P, the Turán number of their product sits at n to the power 3/2, up to constants that depend on T and P but not on n. To see what that exponent means, compare it to the total: a graph on n vertices could in principle have about n squared edges, roughly n times as many. So the forbidden pattern costs you almost everything. What Bradač and colleagues could not do was replace the path with an arbitrary second tree, and they wrote down that generalization as a conjecture.

The star-flip construction

Wang and Yang do not attack products of trees directly. Instead they define a wider family of graphs and prove the bound for all of them. Start with a tree, which they call the seed. Then apply a sequence of local operations, each one duplicating a vertex in a controlled way. Graphs you can build this way they call r-star-flip graphs, where r is an integer at least 2 that tracks how much duplication is allowed. Every such graph, they show, satisfies ex(n, H) = O(n to the power 2 minus 1/r).

The conjecture follows because every Cartesian product of two trees turns out to be a 2-star-flip graph, and plugging r equals 2 into the formula gives exactly the exponent 3/2. The authors note that the star-flip family is strictly larger: it contains graphs that are not products of two trees at all, so the theorem covers cases nobody had asked about. As a second dividend, the same framework produces a fresh proof of a theorem of Zoltán Füredi, which says that a bipartite pattern in which at most one vertex on one side has degree above r also obeys the n to the 2 minus 1/r bound.

The engine underneath is a probabilistic argument. There is a standard technique in this field called a branching random walk on a tree: you drop a walker into a dense graph, let it step to random neighbors following the shape of the tree, and argue that with positive probability the walk traces out a genuine copy of the tree. Trees are easy this way precisely because they have no loops, so nothing has to match up twice. Products of trees do have loops, which is the whole difficulty. Wang and Yang's contribution is what they call a conditional-resampling procedure: it extends the random walk from the seed tree to a random map of the entire star-flip graph, while keeping the original branching-walk distribution intact on every piece of the structure that is still, in their term, live.