This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pse …

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in …

It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane …

This question is hopelessly vague, but here goes: Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined not …

Informal Statement In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a ro …

Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Fi …

I was always fascinated by this nice and easy to state question. I wonder if any progress has been made on it (except for proving it for six). Do you know any related results? For …

How fast can an algorithm tell if an integer is square-free? I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and one …

$\bf Definition.$ We define the space bounded communication in the following way. A and B are supernatural beings capable of computing anything but they only have a limited amount …

Qiaochu Yuan in his answer to this question recalls a blog post (specifically, comment 16 therein) by Terry Tao: For instance, one cannot hope to find an algorithm to determine …

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed! Given a bipartite graph $G$ of $n$ vertices, how many …

There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led …

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly. The best example of this is probably the traveling salesman problem, for which extraordinari …

A very interesting Robertson-Seymour (graphs minors) theorem says: Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the fo …

Cardinal Equivalence Theorem For each boolean formula, |quantifications| = |assignments|. The set of valid quantifications has some cardinality, call that |Q(B)|. The set of sa …