# 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.

**5**

votes

**5**answers

1k views

### Bound on cardinality of a union

Suppose I have n finite sets A1 through An contained in some fixed set S, and I am given non-negative integers N and N1 through Nn such that each Ai has cardinality N, and each k-tuple intersection ...

**15**

votes

**2**answers

810 views

### Is there any meaning to a “nice bijective proof?”

From Zeilberger's PCM article on enumerative combinatorics:
The reaction of the combinatorial enumeration community to the involution principle was mixed. On the one hand it had the universal ...

**0**

votes

**3**answers

403 views

### Definition of longest common subsequences

Edit: I realized that I was confusing subsequences and substrings out of absent-mindedness. I've changed the post to reflect this. My question still stands.
I was shown this research problem: If x is ...

**15**

votes

**3**answers

1k views

### Injective proof about sizes of conjugacy classes in S_n

It's not hard to count the number of permutations in a given conjugacy class of Sn. In particular, the number of permutations in Sn whose cycle decomposition has ci i-cycles is n!/(Πi=1n ci!ici). ...

**10**

votes

**10**answers

1k views

### Algorithmic Combinatorics resources?

Some branches of combinatorics lend themselves naturally to algorithms; graph theory is a natural example. However, straight-up enumerative combinatorics relies much more on analytic and algebraic ...

**6**

votes

**3**answers

398 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

**3**answers

836 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?

**7**

votes

**3**answers

710 views

### “Plateaus” to watch out for

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

**1**answer

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

**1**answer

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

**2**answers

485 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

**3**answers

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

**4**answers

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

**6**answers

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

**2**answers

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

**2**answers

393 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

**5**answers

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

**3**answers

7k views

### Is 8 the largest cube in fibonacci sequence?

Can you prove that 8 is the largest cube in fibonacci sequence?

**15**

votes

**5**answers

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

**3**answers

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

**1**answer

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

**3**answers

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

**1**answer

497 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

**3**answers

760 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

**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 ...

**13**

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 ...

**12**

votes

**3**answers

810 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

**2**answers

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

**1**answer

460 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

**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 ...

**6**

votes

**5**answers

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

**3**answers

884 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 ...

**17**

votes

**4**answers

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

**9**answers

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

**5**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 ...

**3**

votes

**3**answers

662 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

**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 ...

**3**

votes

**2**answers

714 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

**1**answer

972 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

**3**answers

931 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

**1**answer

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

**2**answers

725 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

**0**answers

1k views

### Ignore this question [closed]

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