For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η*_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η*_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.
For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.
This record contains a short preliminary note (TeX source and PDF), Python code and its output, on the question posed in Section 11 of H. Monterde, H. Pal and S. Kirkland, "Laplacian quantum walks on blow-up graphs" (Linear Algebra Appl., 2025, doi:10.1016/j.laa.2025.10.001; numbering of arXiv:2504.11585v1): whether their Theorem 10 (Laplacian perfect state transfer after adding a matching inside the copies of a vertex in the blow-up of n copies of a graph, n divisible by 4) holds for the adjacency matrix. The same question is Problem 10 in H. Monterde's PhD thesis "Quantum pure state transfer" (University of Manitoba, 2025). For matchings whose edges join twin vertices of the blow-up and even n, the note proves that adjacency perfect state transfer between the ends a, b of an added edge forces the matching to cover every neighbour of a, and gives parity conditions on the uncovered vertices. Consequently a nonempty matching inside the copies of a single non-isolated vertex never gives adjacency perfect state transfer, for every graph and every even n. These results, and exact computations on small graphs supporting a conjecture that all sets of copies must be perfectly matched (finite computations only), are the parts claimed as new; a literature search in October 2026 found no earlier treatment of them, which does not establish that none exists. When every set of copies carries a perfect matching (a lexicographic product G[(n/2)K_2]), the note shows that for n divisible by 4 adjacency perfect state transfer between the ends of an added edge occurs if and only if the adjacency eigenvalue support of the vertex is integral, at time pi/2. This is not claimed as new: since G[(n/2)K_2] is isomorphic to Z[K_2], where Z is the blow-up of n/2 copies of G, it follows in a few lines from Proposition 6.3 of A. S. Árnadóttir and K. Guo (arXiv:2608.20476), and its sufficiency for integral graphs is a special case of a lemma of Ge, Greenberg, Perez and Tamon (arXiv:1009.1340). The criterion used for perfect state transfer between adjacent twins is a special case of a theorem of Kirkland, Monterde and Plosker (arXiv:2201.02720). When the matching lies inside the sets of copies, the graphs are edge-perturbed blow-ups in the sense of Monterde and Pal (arXiv:2505.07982v5, Section 9); their Theorem 20 concerns states orthogonal to the all-ones vector of a set of copies and does not cover vertex states. This is a personal hobby/independent research record in which AI was used for exploration, drafting proof candidates, checking and writing; it has not been peer-reviewed by human experts.
Answering a question of Claudet, we prove that the uniformly random graph G∼G(n,1/2) is Ω(n)-vertex-minor universal with high probability. That is, for some constant α≈0.911, any graph on any αn specified vertices of G can be obtained as a vertex-minor of G. This has direct implications for quantum communications networks: an n-vertex k-vertex-minor universal graph corresponds to an n-qubit k-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any k qubits using only local operations and classical communications.
We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number Rvm(k) to be the smallest value n such that every n-vertex graph contains an independent set of size k as a vertex-minor. Supported by our main result, we conjecture that Rvm(k) is polynomial in k. We prove Ω(k2)≤Rvm(k)≤2k−1.
We study the all-state noise threshold η_b(C_m ⊗ C_n) of the product of two regular odd n-cycle (KCBS-type) scenarios in ℝ³, with every context encoded by two bits and local white noise of the same strength on each factor. The threshold is bounded below by the single-cycle thresholds (product states) and by the maximum M_face(m,n) of the threshold over the two-qubit faces v_j^⊥ ⊗ w_k^⊥. We prove that, for all odd m ≥ 9 and n ≥ 5, the face maximum strictly exceeds the single-cycle threshold of C_m (for m ≥ 13 via the published completeness theorem of Araújo et al. for the n-cycle inequalities). Hence entanglement makes C_m ⊗ C_n strictly more robust than both factors for all odd m, n ≥ 9, and the face maximum is at least of order c/m: liminf_m m·inf_n M_face(m,n) ≥ 3√6·π/8 = 2.8857371… > 2 = lim_m m·E(m); no upper bound of order 1/m is proved. The proof uses one Clauser–Horne witness whose violation reduces to a 2×2 form. On each face a six-bit marginal, the CHSH window, is a CHSH test with visibility (1 − η′)², η′ = η/(2 − η); after this reduction Landau's bound gives the closed lower bound Φ(g_m, g_n) = 2(1 − u)/(2 − u), u = (1 S)^(−1/4). For KCBS × KCBS the face threshold equals the window value exactly, M_face(5,5) = 0.26560777045727252964 (a root of an explicit octic), while for 13 pairs (m,n) the face maximum provably exceeds the window value through a second, Clauser–Horne branch whose value stays bounded away from zero as n → ∞. Pure face dominance fails for C₅ ⊗ C₁₁; we formulate a two-regime conjecture and give the numerical evidence for it, together with the known rigorous upper bounds for all states. For KCBS × KCBS we reduce the all-state upper bound to a positivity hypothesis at noise 1/4 on the non-window facets of the noncontextual polytope, verified exactly on all known facet orbits (flip images checked for the lists of 156 and 437 orbits); under it η_b(C₅ ⊗ C₅) = M_face(5,5), the window facets being settled exactly. The stronger hypothesis at the single-cycle threshold η_b(C₅) is false: at least 25 facet orbits outside the window class are violated beyond η_b(C₅), the largest violating noise, attained by two of them, being t_max ∈ [0.2485455, 0.2485456), the lower end being the noise level up to which a planar singlet violates them (numerically its threshold). All values refer to local bit noise and the regular realisation; several of them change under other noise models. Checkers, certificates and cone covers: https://doi.org/10.5281/zenodo.23204387. Lean library (release 1.4.0): https://doi.org/10.5281/zenodo.23204263
The parallel repetition theorem states that, for any two-prover game with value 1−ϵ (for, say, ϵ≤1/2), the value of the game repeated in parallel n times is at most (1−ϵc)Ω(n/s), where s is the answer's length (of the original game) and c is a universal constant [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803]. Several researchers asked whether this bound could be improved to (1−ϵ)Ω(n/s); this question is usually referred to as the strong parallel repetition problem. We show that the answer to this question is negative. More precisely, we consider the odd cycle game of size m, a two-prover game with value 1−1/2m. We show that the value of the odd cycle game repeated in parallel n times is at least 1−(1/m)⋅O(n). This implies that, for large enough n (say, n≥Ω(m2)), the value of the odd cycle game repeated in parallel n times is at least (1−1/4m2)O(n). Thus the following hold. 1. For parallel repetition of general games, the bounds of (1−ϵc)Ω(n/s) given in [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803; T. Holenstein, in Proceedings of STOC 2002, ACM, New York, 2002, pp. 767–775] are of the right form, up to determining the exact value of the constant c≥2. 2. For parallel repetition of XOR games, unique games, and projection games, the bounds of (1−ϵ2)Ω(n) given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] (for XOR games) and in [A. Rao, in Proceedings of STOC 2008, ACM, New York, 2008, pp. 1–10] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game, the bound of 1−(1/m)⋅Ω~(n) given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least 1−ϵ2 satisfiable from instances that are at most 1−(2/π)⋅ϵ satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.