{"id":"arxiv/2607.27407","url":"https://arxiv.org/abs/2607.27407","tags":["math.CO","cs.DM"],"score":0,"title":"On $\\varepsilon$-Matrix Product Factorization of graphs","domain":"math.CO","source":"arxiv","authors":["Farzad Maghsoudi","Bobby Miraftab","Sho Suda"],"reviews":0,"subject":"math.CO","summary":"We introduce an approximate version of matrix product factorization for graphs. A simple graph $G$ on $n$ vertices is said to admit an $\\varepsilon$-matrix product factorization if there exist simple graphs $H$ and $K$ on the same vertex set such that $A(H)A(K)$ and $A(G)$ disagree in at most $\\varepsilon n^{2}$ entries. This Hamming-type relaxation preserves, outside the error set, the exact interpretation of each edge as having a unique $H$-then-$K$ two-step witness. We establish equivalent matrix, and witness formulations, showing that the sets $N_H(w)\\times N_K(w)$ form an approximate…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-29","reactions":{}}