BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Liviu Ilinca contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We give an alternative proof of a conjecture of Bollobás, Brightwell and Leader, first proved by Peter Allen, stating that the number of boolean functions definable by 2-SAT formulae is $(1+o(1))2^{\binom{n+1}{2}}$. One step in the proof determines the asymptotics of the number of "odd-blue-triangle-free" graphs on $n$ vertices.
With $G_k(n)$ the number of functions of $n$ boolean variables definable by $k$-SAT formulae, we prove that $G_3(n)$ is asymptotic to $2^{n+\binom{n}{3}}$. This is a strong form of the case $k=3$ of a conjecture of Bollobás, Brightwell and Leader stating that for fixed $k$, $\log_2 G_k(n)\sim \binom{n}{k}$.