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.

5
votes
5answers
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
2answers
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
3answers
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
3answers
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
10answers
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
3answers
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
3answers
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
3answers
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
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
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
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
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
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
7k 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
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
3answers
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
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
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
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
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
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
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
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
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
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
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
1answer
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
3answers
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
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
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
0answers
1k views

Ignore this question [closed]

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