Infinite induced-system freeness conjecture

At least 15 years old · documented by

Let F\mathcal{F} be a possibly infinite set of systems of induced equations, and let a Boolean function be F\mathcal{F}-free when it contains no induced solution of any system in F\mathcal{F}. Infinite induced-system conjecture. For every possibly infinite set F\mathcal{F} of systems of induced equations, the property of being F\mathcal{F}-free is testable with one-sided error. This is motivated by the analogy with induced-free graph and hypergraph properties; the source raises it as an open conjecture, while noting that bounded-rank variants may be more plausible.

References

Primary source

Arnab Bhattacharyya, Elena Grigorescu and Asaf Shapira, “A Unified Framework for Testing Linear-Invariant Properties”, arXiv:1010.5016 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.