All Questions
Tagged with combinatorics or co.combinatorics
11,021 questions
6
votes
3
answers
1k
views
Is there a software package that does Schubert Calculus computations?
Is there a good software package for doing computations in the cohomology ring of Grassmannians? Things like, I can write down a polynomial in, in fact, special Schubert classes, but it's one where ...
- 16k
11
votes
6
answers
3k
views
Regular languages and the pumping lemma
Let's say that I want to prove that a language is not regular.
The only general technique I know for doing this is the so-called "pumping lemma", which says that if $L$ is a regular language, then ...
- 44.8k
16
votes
6
answers
3k
views
analog of principle of inclusion-exclusion
When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...
- 2,150
14
votes
3
answers
1k
views
Is there a matrix whose permanent counts 3-colorings?
Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean:
Kirchhoff's theorem says that if you ...
- 12.6k
36
votes
2
answers
13k
views
Mean minimum distance for N random points on a one-dimensional line
Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...
- 811
3
votes
1
answer
495
views
Dance battles and de Bruijn sequences
I hope this doesn't fall under the "not interesting to mathemeticians" category.
I'm attempting to solve one of the facebook engineering puzzles. Essentially, the idea is that two dancers do a ...
- 131
23
votes
6
answers
2k
views
Is there a topological description of combinatorial Euler characteristic?
There are a collection of definitions of "combinatorial Euler characteristic", which is different from the "homotopy Euler characteristic". I will describe a few of them and give some references, and ...
- 54.6k
7
votes
5
answers
6k
views
Definition of infinite permutations
I've been trying to find a definition of an infinite permutation on-line without much success. Does there exist a canonical definition or are there various ways one might go about defining this?
The ...
- 1,155
6
votes
3
answers
1k
views
Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.
Aside from the Desargues graph, are there nice (at least vertex-transitive), small (say, less than 60 vertices), cubic, bipartite graphs with girth at least 6 and no 8-cycles? (or, even better, no ...
22
votes
8
answers
2k
views
Points and lines in the plane
Does a positive real number $k\geq1$ exist such that for every finite set $P$ of points in the plane (with the property that no three points of $P$ lie on a common line and $|P|\geq3$), one can choose ...
- 319
23
votes
4
answers
3k
views
Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.
Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$...
- 118k
16
votes
9
answers
3k
views
What is the Tutte polynomial encoding?
Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...
- 12.6k
15
votes
6
answers
2k
views
Can one make Erdős's Ramsey lower bound explicit?
Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...
- 2,967
4
votes
3
answers
830
views
Is there a "universal LYM inequality?"
This question is based on a blog post of Qiaochu Yuan.
Let P be a locally finite* graded poset with a minimal element, and w be a weight function on the elements of P. Suppose that the total weight ...
- 12.6k
26
votes
5
answers
2k
views
Cauchy-Schwarz and pigeonhole
I've occasionally heard it stated (most notably on Terry Tao's blog) that "the Cauchy-Schwarz inequality can be viewed as a quantitative strengthening of the pigeonhole principle." I've certainly seen ...
- 12.6k
3
votes
2
answers
884
views
Is the "diagonal" of a regular language always context-free?
That's very poor wording, so let me be more precise. Suppose $L$ is an unambiguous regular language on an alphabet $\{a_1, \dots, a_n\}$, and suppose to each letter of the alphabet we associate two ...
- 118k
6
votes
1
answer
1k
views
Specializations of Schur functions at consecutive integers
Given a partition λ = (λ1, λ2, ..., λn) denote with sλ the associated Schur function.
There exists a nice product formula for the principal specializations:
sλ...
- 1,412
5
votes
3
answers
1k
views
What is the expected number of maximal bicliques in a random bipartite graph?
Maximal Biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.
Given a bipartite graph $G=(V_{1}\cup V_{2}, E)$ where $|V_{1}|=|V_{2}|$ with ...
- 153
15
votes
1
answer
715
views
What are the Schur functions of the eigenvalues of a non-negative integer matrix counting?
Let A be a non-negative integer square matrix with eigenvalues x1, x2, ... xn. Any symmetric function of these eigenvalues with integer matrices is an integer. I'm aware of the following results ...
- 118k
11
votes
2
answers
1k
views
Finding monochromatic rectangles in a countable coloring of $R^{2}$
Given a countable coloring of the plane, is it always possible to find a monochromatic set of points $\left\{ \left(x,y\right),\left(x+w,y\right),\left(x,y+h\right),\left(x+w,y+h\right)\right\} $ (the ...
- 271
0
votes
0
answers
2k
views
Ignore this question [closed]
This question is a hacky way to create some tags for you to use. Move along.
