Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with co.combinatorics
Search options not deleted
user 30800
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
3
votes
Accepted
All possible linear combinations of positive half-integers with coefficients +/- 1
Indeed it is the Subset Sum Problem (or closely related to it). This problem asks essentially whether $\mu(P)>0$.
It is only weakly NP-complete, and there is a pseudopolynomial dynamic-programming
alg …
- 1,083
8
votes
Tiling a rectangle with a hint of magic
There is an unpublished note on this theorem from 1987 by Edgser W. Dijkstra, On a Problem transmitted by Doug McIlroy, see also this summary. He explains how the proof that uses complex double integr …
- 1,083
6
votes
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for …
- 1,083
1
vote
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
The better analogy when the markers are distinct is not Sokoban, but the 15-puzzle. It is even on an undirected graph.
All my remarks below are about the undirected version. ADDITION: At the end ther …
- 1,083
4
votes
Minimal graphs with a prescribed number of spanning trees
No answer, but a related question:
The number $n$ of spanning trees in a graph with $k+1$ vertices is the determinant of a $k\times k$ matrix with integer entries between $-1$ and $k$.
For given $ …
8
votes
Is the empty graph a tree?
I checked Reinhard Diestel's textbook on Graph Theory. p.2
A graph of order 0 or 1
is called trivial. Sometimes, e.g. to start an induction, trivial graphs can
be useful; at other times they form sil …
- 1,083