9
votes
5answers
792 views

Examples of ubiquitous objects that are hard to find?

I've been wrestling with a certain research problem for a few years now, and I wonder if it's an instance of a more general problem with other important instances. I'll first describe a general ...
6
votes
1answer
294 views

Generating functions with all non-zero coefficients equal to one

Inspired by this question, I have been wondering if there are any useful generating functions with all non-zero coefficients equal to one. Obviously, the trivial generating function $\frac{1}{1-x}$ ...
8
votes
4answers
407 views

Order-independent properties arising naturally in mathematics

The motivation for the following question comes from finite model theory, but it is not a technical question about this field, and it is particularly directed at people working in other fields. It ...
9
votes
2answers
409 views

Has there been any application of tensor species?

Joyal's combinatorial species, endofunctors in the category of finite sets with bijections $\mathbf B$ have found numerous applications. One generalisation is given by so-called "tensor species" ...
5
votes
9answers
1k views

Examples of two different descriptions of a set that are not obviously equivalent?

I am teaching a course in enumerative combinatorics this semester and one of my students asked for deeper clarification regarding the difference between a "combinatorial" and a "bijective" proof. ...
30
votes
2answers
2k views

Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...
3
votes
3answers
1k views

Examples of Super-polynomial time algorithmic/induction proofs?

In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form: -The proof moves through stages -An invariant is shown to hold by induction from previous stages ...
18
votes
8answers
1k views

Cryptomorphisms

I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are Topological Spaces. These can be defined in terms of open sets, ...
32
votes
15answers
6k views

Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication "If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true." for ...
4
votes
2answers
234 views

Is there a poset with 0 with countable automorphism group?

Is there a poset P with a unique least element, such that every element is covered by finitely many other elements of P (and P is locally finite -- actually, per David Speyer's example, let's say that ...
33
votes
12answers
5k views

Combinatorial results without known combinatorial proofs

Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell ...
0
votes
3answers
215 views

Where to find nice diagrams of trees and other graphs? [closed]

Are there some publicly available, vector format diagrams of trees and other graphs? They aren't hard to make, but they sure do take a lot of time (for me).