Blow-up trick in combinatorics

Veronica Phan* · 2026

Read Blow-up trick in combinatorics by Veronica Phan* (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06725.txt.

Introduction

Veronica Phan extends the graph blow-up operation to a broader combinatorial setting and discusses what it could be used for. In graph theory, blowing up a graph replaces each vertex with several copies of itself, and copies are joined exactly when the original vertices were joined. Phan generalizes that copying idea beyond graphs and explores potential applications of the extended construction.

Catalog record

CREATORVeronica Phan*
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06725

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Blow-up trick in combinatorics Thanks: *Ho Chi Minh City; email: [email protected] Veronica Phan* Abstract . Blow-up in graph theory is a procedure in which each vertex is replaced by copies of itself, and two copies are adjacent if and only if the original vertices are adjacent. In this paper, we extend the concept of graph blow-up to a more general combinatorial context and discuss its potential applications. 1. Blow-up of a graph Given a graph G=(V,E) , a blow-up of G is obtained by replacing each vertex v\in V with an independent set of vertices I_{v} ( I_{v} could be empty), and for every edge uv\in E , adding all possible edges between I_{u},I_{v} . More formally, the resulting graph is G^{\prime}=\left(\bigcup_{v\in V}I_{v},\bigcup_{uv\in E}I_{u}\times I_{v}\right) . What is special about a blow-up of a graph? From the construction, we see that the blow-up of a graph can preserve certain local properties of the original graph, such as the clique number \omega(G) . This observation is reminiscent of Turán’s theorem, but can this simple procedure help us solve it? Theorem 1 (Turán’s theorem, simple form) . Every graph with n vertices that does not contain K_{r+1} as a subgraph (or K_{r+1} -free) has no more than \left(1-\frac{1}{r}\right)\frac{n^{2}}{2} edges. Assume G=(V,E) is a K_{r+1} -free graph with |V|=n . We try to blow-up G by replacing each vertex v\in V with an independent set I_{v} of size |I_{v}|=c_{v} . The resulting graph has \sum_{v\in V}c_{v} vertices and \sum_{uv\in E}c_{u}c_{v} edges. By Turán’s theorem, we expect that \sum_{uv\in E}c_{u}c_{v}\leq\left(1-\frac{1}{r}\right)\frac{\left(\sum_{v\in V}c_{v}\right)^{2}}{2} . Let x_{v}=\frac{c_{v}}{\sum_{v\in V}c_{v}} , then \sum_{v\in V}x_{v}=1,0\leq x_{v}\leq 1,\forall v\in V . Divide both sides of the inequality by \left(\sum_{v\in V}c_{v}\right)^{2} , we obtain \sum_{uv\in E}x_{u}x_{v}\leq\frac{1}{2}\left(1-\frac{1}{r}\right) This is precisely the key inequality T. S. Motzkin and E. G. Straus [ 1 ] used to prove Turán’s theorem. Theorem 2 (Motzkin-Straus theorem) . Let G=(V,E) be a K_{r+1} -free graph. We assign each vertex v\in V a nonnegative real number x_{v} such that \sum_{v\in V}x_{v}=1 . Then we have \sum_{uv\in E}x_{u}x_{v}\leq\frac{1}{2}\left(1-\frac{1}{r}\right) Proof (sketch). We consider maximizing \mathcal{L}_{G}(x_{v})_{v\in V}=\sum_{uv\in E}x_{u}x_{v} . Assume a,b are not adjacent in G , define G_{a},G_{b} be the graphs created from G by removing the vertex b,a from V , respectively. We assign nonnegative number (x^{a}_{v})_{V\setminus\{b\}} to vertices of G_{a} as follow: x^{a}_{a}=x_{a}+x_{b},x^{a}_{v}=x_{v},v\neq a , similarly for G_{b} . Then (x_{a}+x_{b})\mathcal{L}_{G}(x_{v})_{v\in V}=x_{a}\mathcal{L}_{G_{a}}(x^{a}_{v})_{v\in V\setminus\{b\}}+x_{b}\mathcal{L}_{G_{b}}(x^{b}_{v})_{v\in V\setminus\{a\}} Thus, we may remove either vertex a or b so that the value of \mathcal{L}_{G}(x_{v})_{v\in V} does not decrease. Repeating this process until every pair of remaining vertices is adjacent, we eventually obtain a complete graph on at most r vertices. The result then follows straightforwardly. ∎ Proof of theorem 1 . We assign each vertex v\in V number \frac{1}{n} , the result follows by theorem 2 . ∎ We have just proved the simple form of Turán’s theorem by blowing up the graph, deriving the key inequality in a natural way, and completing with a simple trick. So why does the blow-up trick work? - Blow-up preserves the important local properties of the object. - Blow-up transforms a discrete problem into a semi-continuous one, allowing us to apply tools from analysis. - By blowing up, we can vary the size of the object, which helps us relate object of different size. 2. Blow-up of hypergraph Now we extend the blow-up trick to the hypergraph setting, specifically to 3 -graph. Let us begin with Turán conjecture [ 2 ] on K^{3}_{4} -free 3 -graph. Conjecture 1 (Turán conjecture, simple form) . Every K^{3}_{4} -free 3 -graph with n vertices has no more than \frac{5}{54}n^{3} edges Similarly to the graph case, given a K^{3}_{4} -free 3 -graph G=(V,E) , we replace each vertex v\in V with an independent set of vertices I_{v} of size |I_{v}|=c_{v} , and for every edge (u,v,w)\in E , we add all possible 3 -edges between I_{u},I_{v} and I_{w} . We then seek to maximize \sum_{(u,v,w)\in E}x_{u}x_{v}x_{w} over all nonnegative real numbers (x_{v})_{v\in V} statisfying \sum_{v\in V}x_{v}=1 . But now the problem becomes more complex become the expression is nonlinear. Moreover, (u,v,w)\notin E does not exclude the possibility that there exists some t\in V such that (u,v,t)\in E , which make the calculation even more complicated. So what is the problem here? We have not added enough information to the blow-up. We need to add 3 -edges of the form (u_{1},u_{2},v_{1}) for u_{1},u_{2}\in I_{u} and v_{1}\in I_{v} , which can be represented as a directed 2 -edge u\rightarrow v . However, we cannot add edges of this type arbitrarily, since the resulting 3 -graph may no longer be K^{3}_{4} -free. Suppose we have the original K^{3}_{4} -free 3 -graph G=(V,E) and the directed graph D=(V,A) describing how the special 3 -edges are added into the blow-up construction. We now determine the forbidden configurations that ensure the resulting graph remains K^{3}_{4} -free: - If u\rightarrow v,v\rightarrow u\in A , then the vertices \{u_{1},u_{2},v_{1},v_{2}\} where u_{1},u_{2}\in I_{u} and v_{1},v_{2}\in I_{v} induced a copy of K^{3}_{4} . Therefore, D must be an oriented graph (in particular, it contains no pair of opposite directed edges). - If u\rightarrow v,u\rightarrow w\in A,(u,v,w)\in E , then the vertices \{u_{1},u_{2},v,w\} where u_{1},u_{2}\in I_{u} induced a copy of K^{3}_{4} . Therefore if (u,v,w)\in E , then at most one of u\to v and u\to w may belong to A . Equivalently, whenever u\rightarrow v,u\rightarrow w\in A , we must have (u,v,w)\notin E . The problem is still complicated, but it now has much more structure. To simplify it (at the cost of no longer addressing the original question directly), we fixed the oriented graph D=(V,A) and add 3 -edge in a suitable way that maximizes the number of edges while still keep the resulting 3 -graph K^{3}_{4} -free. A natural construction is the following: (u,v,w)\in E if and only if the vertices \{u,v,w\} induced a subgraph of D with at least 2 edges and containing no copy of the directed graph S=(\{a,b,c\},a\rightarrow b,a\rightarrow c) . The only missing condition for the resulting 3 -graph G=(V,E) to be K^{3}_{4} -free is that D does not contain directed cycle of length 4 . This is essentially the beautiful construction of K^{3}_{4} -free 3 -graph due to Fon-der-Flaass [ 3 ] , we recover it simply by blowing up the 3 -graph and observing what happens. Now we simplify the problem further by ignoring the condition that D does not contain a directed cycle of length 4 , at the cost that the resulting graph may no longer K^{3}_{4} -free. Given a oriented graph D=(V,A) and 3 -graph G=(V,E) constructed as above, we seek to maximize \frac{\sum_{(u,v,w)\in E}c_{u}c_{v}c_{w}+\sum_{u\rightarrow v\in A}\frac{c_{u}(c_{u}-1)}{2}c_{v}}{\left(\sum_{v\in V}c_{v}\right)^{3}} over all nonnegative integer (c_{v})_{v\in V} Let x_{v}=\frac{c_{v}}{\sum_{v\in V}c_{v}} and suppose that the c_{v} are arbitrary large, then the above expression becomes asymptotically \sum_{(u,v,w)\in E}x_{u}x_{v}x_{w}+\frac{1}{2}\sum_{u\rightarrow v\in A}x_{u}^{2}x_{v} Now we are able to obtain the bound \frac{3}{32} for the above expression. This is not the desired bound of \frac{5}{54} since we have removed an important condition. Nevertheless, it is still equivalent to a strong result of Alexander A. Razborov [ 4 ] stating that the edge density of a Fon-der-Flaass graph is at least \frac{7}{16}(1-o(1)) . We generalize our previous construction as follow:

Read the complete text