A four-edge obstruction to submodular separation of quadratic Boolean monomial images: a counterexample to Brakensiek-Gopi-Guruswami Conjecture 3.33 (arXiv:1902.04740; ECCC TR19-013)

Myeongjin Kang

Abstract

Conjecture 3.33 is false at (r,d) = (2,5): no integer- (indeed real-) valued submodular function on {0,1}^16 is negative exactly on the degree-2 monomial image of {0,1}^5.

AI-assisted research preprint. The scoped main statement has a Lean certificate. Internal AI review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for exact qualifications and formalization limits.

2

Supplementary files

  • proof-sources.json6.1 KBOpen
  • extract_sources.py481 BOpen

Comments

Submitted by Myeongjin Kang. Related MathDB problem 341850. Proof sources are attached as proof-sources.json (gzip-compressed, base64-encoded file contents); extract_sources.py reconstructs all archived files. Original archive SHA-256: 441cb79ec825366931cdee6221b99e4b3235dd2145f343565e8df2fb2bd13db8.

Version history

Discussion 0