Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

6
votes
3answers
400 views

Prime numbers and strings of symbols

Suppose you have N symbols (e.g. "1","2",...,"N" or "a","b",...,"$") and a string of these symbols (say, the first trillion digits of pi). Then does there exist a prime number whose N-ary ...
7
votes
3answers
839 views

How can we count lines in an n-x-n rectangular array?

Is there a formula for the number of lines that contain exactly two points through an n x n rectangular array of points?
6
votes
3answers
723 views

“Plateaus” to watch out for [closed]

I'm a lot earlier in my math education that most of the people on this site. Currently I'm studying computer science, and I'm interested in looking into statistical and optimization applications, as ...
4
votes
1answer
304 views

Number of subdivisions of an n-gon

Suppose I have a regular n-gon. I want to draw some noncrossing diagonals to subdivide it into smaller polygons. In how many ways can I do this? The vertices are unlabeled, so I don't distinguish ...
3
votes
1answer
384 views

Any work on the Adams-Watters triangle?

Does anyone know whether any arithmetical or asymptotic results have been obtained about the Adams-Watters triangle?
6
votes
2answers
486 views

Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?

I ran into this obstacle in a harmonic analysis problem; I know epsilon about coloring problems. Is it possible to finitely color Z^2 so that the points (x,a) and (a,y) are differently colored for ...
10
votes
3answers
645 views

A “round” lattice with low kissing number?

Historically, the lattices with high density were studied intensively, e.g. E_8 lattice or Leech Lattice. However, there are situations that lattices with low kissing number are required. Specifically,...
15
votes
4answers
2k views

Dyck paths on rectangles

The number of Dyck paths in a square is well-known to equal the catalan numbers: http://mathworld.wolfram.com/DyckPath.html But what if, instead of a square, we ask the same question with a rectangle? ...
4
votes
6answers
549 views

Placing checkers with some restrictions

We are going to put n checkers on an (n x n) checkers board, with the following restrictions: 1) In each column there is EXACTLY one checker. 2) For i=1,2,...,(n-1), the first i rows cannot have ...
3
votes
2answers
740 views

Helm's improvement to Beck-Fiala theorem

Beck-Fiala theorem states that if X is a finite set and H is any family of subsets of X, in which every vertex occurs in at most d sets of H, then there is a a function f:X->{±1} such for every ...
6
votes
2answers
396 views

Asymptotics of the number of compositions whose summands are the divisors of a number?

Let $n$ be a natural number. Let $dc(n)$ be the number of compositions of $n$ where the summands are required to be in the set of divisors of $n$. Standard lore in analytic combinatorics yields the ...
14
votes
5answers
696 views

Number of metric spaces on N points

Given $X = \{x_1, ..., x_n\}$, how many collections $C$ of subsets of $X$ are there such that $C$ is the listing of all open balls of some metric space? The first nontrivial example is $n=3$; let's ...
24
votes
3answers
8k views

Is 8 the largest cube in fibonacci sequence?

Can you prove that 8 is the largest cube in fibonacci sequence?
15
votes
5answers
1k views

Pairs of shortest paths

It is known that the binomial coefficient $2n \choose n$ is equal to number of shortest lattice paths from $(0,0)$ to $(n,n)$. The Catalan number $\frac{1}{n+1} {2n\choose n}$is equal to the number of ...
7
votes
3answers
2k views

Special cases for efficient enumeration of Hamiltonian paths on grid graphs?

While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time ...
17
votes
1answer
732 views

Is there a Murnaghan-Nakayama Rule for GL(n,q)?

The Murnaghan-Nakayama rule for S_n is a combinatorial rule to compute the irreducible characters of the symmetric group. Is there a q-analogue of this rule for GL(n,q) to compute the irreducible ...
5
votes
3answers
1k views

Asymptotics of a hypergeometric series/Taylor series coefficient.

I was planning on figuring this problem out for myself, but I also wanted to try out mathoverflow. Here goes: I wanted to know the asymptotics of the sum of the absolute values of the Fourier-Walsh ...
2
votes
1answer
499 views

Chains intersecting antichains in finite posets

I feel a little embarrassed to be asking this question here, since I think it should be much easier than I'm making it, but here goes: Given a finite poset P, does there necessarily exist some chain ...
5
votes
3answers
762 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 ...
10
votes
6answers
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 ...
13
votes
6answers
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 ...
12
votes
3answers
811 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 ...
28
votes
2answers
6k 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 ...
3
votes
1answer
461 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 ...
22
votes
6answers
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 ...
6
votes
5answers
3k 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 ...
6
votes
3answers
885 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
8answers
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 ...
17
votes
4answers
2k 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$...
11
votes
9answers
2k 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
votes
5answers
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 ...
3
votes
3answers
663 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 ...
19
votes
5answers
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 ...
3
votes
2answers
715 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 ...
6
votes
1answer
974 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λ...
5
votes
3answers
933 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 ...
13
votes
1answer
603 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 ...
7
votes
2answers
731 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 ...
0
votes
0answers
1k views

Ignore this question [closed]

This question is a hacky way to create some tags for you to use. Move along.