0
$\begingroup$

I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the information that it is Boolean?

I'm presently using the variables as vertices with an edge between two if they are present in the same monomial. This does not take into account that the function is Boolean. I thought of 2-colorings of the vertices of a hypercube, but that does not really put any restriction on the graph. For my problem, I would need to use some property of the graph that results from the function being Boolean. Can someone provide some ideas to do this?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Your question is extremely vague. Perhaps you would like to share the actual problem you are interested in? $\endgroup$
    – Yuval Filmus
    Jan 20, 2022 at 15:27
  • $\begingroup$ @YuvalFilmus I am trying to classify all flat and homogeneous Boolean functions (i.e. every monomial has the same degree and the function has a flat Fourier spectrum). I have an idea to do this via representing the function as a graph, since I see that product and composition of two Boolean functions has nice interpretations in graph theory (using join of graphs). I wish to take an arbitrary such Boolean function, look at a graph representation and deduce properties of the graph. But I cant think of any such graph representation that uses the fact that the function is Boolean. $\endgroup$
    – kleinbottle
    Jan 20, 2022 at 15:32
  • $\begingroup$ What do you mean by flat Fourier spectrum? $\endgroup$
    – Yuval Filmus
    Jan 20, 2022 at 17:34
  • $\begingroup$ By flat spectrum I mean all the Fourier coefficients have the same magnitude. $\endgroup$
    – kleinbottle
    Jan 20, 2022 at 17:48
  • $\begingroup$ The degree 2 case is known. For larger degrees, your graph loses a lot of information. It might be better to construct a hypergraph instead, perhaps even coloring the hyperedges according to sign. $\endgroup$
    – Yuval Filmus
    Jan 20, 2022 at 17:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.