Find the number of boolean functions of n variable that satisfy the following condition

For how many boolean functions is this true? The length of the shortest disjunctive normal form of that functions is equal to 2^(n-1). And the the number of variable entries in the minimal dnf of that functions is equal to n*(2^(n-1)-1). Answer AttributionSource : Link , Question Author : Ani Kar , Answer Author : … Read more

The properties of Pos

Given n\in\mathbb{N}, and f:\mathbb{N}^*\rightarrow \mathbb{N}, let define Pos as: Pos(f)(n)= |\{x \leq n, f(x)=f(n)\}| When given n\in\mathbb{N}, this function gives the ‘position’ of n in the list of the elements of f^{-1}(f(n)). Therefore, f injective \Leftrightarrow Pos(f)=1_{\mathbb{N}}, and f constant \Leftrightarrow Pos(f)=Id One can show that Pos(Pos(Pos(f))=Pos(f) for all f\in\mathcal{F}(\mathbb{N}^*,\mathbb{N}), and hence that Pos\circ Pos … Read more

Level sets of function of inner products of vectors on hypercube

Let $H = \{ 0, 1\}^d$ be the $d$-th Cartesian product of $\{0, 1\}$ in $\mathbb{R}^d$. Suppose $v_1, \ldots, v_k$ are $k$ vectors in $H$ in general position. We define function $F \colon H^{k}\rightarrow \mathbb{R}$ as \begin{align} F (u_1, u_2, \ldots, u_k) = \sum_{i,j = 1}^k f( | \langle v_i, u_j \rangle |), \end{align} where … Read more

Separate a special poset by function

Assume A=∏ni=1{0,1}, i.e. element (a1,⋯,an)=a∈A is n-tuples like (1,0,1,⋯). There is an obvious partial order on the A: say a<b for a,b∈A if and only if ∀i∈{1,⋯,n} ai≤bi. Note this is only a partial order. We define the order-preserved partition (A1,A2) of A: A1∪A2=A, A1∩A2=∅, and for any a∈A1,b∈A2, we have a≱, i.e. there is … Read more

what’s an upper bound on the size of the largest biclique in random bipartite graph?

I am not an expert in random graph but I need the following result and I couldn’t find any reference on this. Let G(X∪Y,p) be a random bipartite graph where the set of edges is X∪Y, X and Y both have cardinality n and p is the proba of adding an edge between each node … Read more

Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an exponential number of triangulations,1 somewhere between $2.6^n$ and $43^n$.) An edge-flip is the operation illustrated below; it requires $e$ to … Read more

Number of different positions of rooks on chessboard

I know that this topic as been mentioned before, but no accurate answer has been provided. Suppose we have to place $n$ rooks on $n \times n$ chessboard so that no one attacks another. How to count the number of different ways to place them up to rotations of the chessboard? I have been trying … Read more

Modification of matching

Suppose i have an n×n random bipartite graph and suppose that i repeat the following process n times. At the start (stage 1) each edge is selected independently with probability p(n), and we output the largest matching M1. In stage 2 all edges are selected randomly again regardless of how they appeared before but this … Read more

An interesting variant on the maximum independent set problem.

Suppose i have a graph G=(V,E) with |V|=n. Furthermore suppose i give you a maximum independent set I in G. Now suppose i obtain a new graph G′ from G by removing a single vertex v∈I from V. Now of course α(G′)∈{|I|,|I|−1} but can we say more? Is it an NP-hard to find a maximum … Read more