# 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,443 questions

**13**

votes

**0**answers

1k views

### Finding a chromatic polynomial by polynomial fitting

I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph ...

**5**

votes

**2**answers

262 views

### Bounds on a partition theorem with ambivalent colors

I've been running into the following type of partition problem.
Given positive integers h, r, k, and a real number ε ∈ (0,1), find n such that if every (unordered) r-tuple from an n ...

**37**

votes

**5**answers

4k views

### Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable.
This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...

**9**

votes

**4**answers

1k views

### Uniqueness in Composition of Polynomials

The following situation came up in my research:
Suppose two functions $f$ and $g$ map $[0,\infty)$ to (a subset of) itself. The function $f$ is linear and $g$ is quadratic, but $g$ is one-to-one on ...

**13**

votes

**1**answer

588 views

### Where do stable Kronecker coefficients live “in nature”?

Background:
For a partition $\lambda$, let $\lambda[N] = (N - |\lambda|, \lambda_1, \lambda_2, \lambda_3, \dots)$, also let $\chi_\lambda$ be the corresponding irreducible character of the symmetric ...

**2**

votes

**1**answer

211 views

### Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?

This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a ...

**15**

votes

**3**answers

5k views

### Number of invertible {0,1} real matrices?

This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...

**7**

votes

**1**answer

660 views

### Counting Eulerian Orientation in a 4-regular undirected graph

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...

**6**

votes

**2**answers

1k views

### Is there a known formula for the number of SSYT of given shape with partition type?

Let $s_{\lambda}$ and $m_{\lambda}$ be the Schur and monomial symmetric functions indexed by an integer partition $\lambda$ ($\ell(\lambda)$ is the number of parts of $\lambda$ and $m_i(\lambda)$ is ...

**5**

votes

**0**answers

468 views

### Is the face poset a Heyting algebra?

Is the face poset of a simplicial or nice enough cellular complex a Heyting algebra in some natural way?
Edited to add: For the benefit of illustration, here's a few face posets:
the boundary of a ...

**18**

votes

**3**answers

4k views

### Number of unique determinants for an NxN (0,1)-matrix

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore will trivially have zero determinant. While it ...

**5**

votes

**1**answer

2k views

### Maximum bipartite graph (1,n) “matching”

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out ...

**3**

votes

**0**answers

260 views

### Algebraic Kneser conjecture?

Recall that Kneser conjecture (now Lovasz theorem) claims that if the family of $k$-subsets (subsets of cardinality $k$) of given $(2k+d)$-set $M$, $d\geq 1$ are colored into $d+1$ colors, then there ...

**7**

votes

**3**answers

2k views

### What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers?

A friend of mine and I were wondering what relationship exists between the partition numbers $p_{n}$ and the Bell numbers $B_{n}$ (and also possibly the Bell polynomials $B_{n,k}(x_1,x_2,\dots,x_{n-k+...

**7**

votes

**4**answers

3k views

### Examples of inductive proofs that can be generalized by transfinite induction

Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial ...

**4**

votes

**2**answers

410 views

### Generalization of permanent definition based on number of permutation cycles

Let $A$ be an $n$ by $n$ matrix and $x$ a free parameter. Define
$$p(A,x)=\sum_{\pi \in S_n} x^{n(\pi)}A_{1\pi(1)}\ldots A_{n\pi(n)},$$
where $\pi$ ranges over the permutation group $S_n$ and $n(\pi)$ ...

**3**

votes

**5**answers

381 views

### Strings and “co-subsequences”

Let $S$ be a string over some alphabet $\Sigma$. It is well known that a substring of $S$ is commonly defined as a sequence of contiguous elements from $S$, while a subsequence of $S$ is a sequence ...

**7**

votes

**1**answer

662 views

### Combinatorics of lattice walks with forbidden points

If I'm not in error, the number of walks on a 2-dimensional integer lattice of length 2n steps from the origin to a point (x,y) has a nice closed form:
${2n \choose n + (x + y)/2}{2n \choose n + (x - ...

**20**

votes

**2**answers

1k views

### Lifting matrices mod 2 to integers.

The following question was motivated by my research.
Consider a $n\times n$ matrix whose elements are $0$'s or $1$'s such that the determinant is odd. The question is: is it possible to assign signs ...

**1**

vote

**1**answer

180 views

### Some extremal problem for uniform hypergraph with fixed number of edges.

Let S = {1, .. ,n}.
Let H = (S, E) be the m-uniform hypergraph with r edges.
Let F(H, k) = #{B | |B| = k, $\exists R \in E, B \cap R = \emptyset$ } -
a number of k-subsets, that doesn't intersect ...

**4**

votes

**1**answer

498 views

### Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S=\{013,026,045,124,156,235,346\}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below.
\[L=\left(...

**43**

votes

**6**answers

17k views

### Is the Jaccard distance a distance?

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any ...

**79**

votes

**17**answers

87k views

### Google question: In a country in which people only want boys [closed]

Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...

**23**

votes

**5**answers

2k views

### What (if anything) happened to Viennot's theory of Heaps of pieces?

In 1986 G.X. Viennot published "Heaps of pieces, I : Basic definitions and combinatorial lemmas" where he developed the theory of heaps of pieces, from the abstract: a geometric interpretation of ...

**5**

votes

**1**answer

377 views

### How to optimize student happiness in group work?

There are $n$ students in a class, and they must be divided into, say, $k$ groups. Each student ranks the other students in order of preference of working together. Is there a way to generally ...

**27**

votes

**5**answers

2k views

### Small simplicial complexes with torsion in their homology?

Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology?
For example, when $p=2$, there is a complex with 6 vertices (...

**11**

votes

**5**answers

4k views

### infinite permutations

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...

**5**

votes

**9**answers

2k views

### Are there any important mathematical concepts without discrete analog?

In "continuous" mathematics there are several important notions such as covering space, fibre bundle, Morse theory, simplicial complex, differential equation, real numbers, real projective plane, etc. ...

**15**

votes

**1**answer

1k views

### Making a non-monotone function monotone

Consider a function $f: \{0,1\}^n \rightarrow \{1..R\}$. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors.
We say there is a ...

**35**

votes

**5**answers

3k views

### Why do wedges of spheres often appear in combinatorics?

Robin Forman writes in "A User's Guide to Discrete Morse Theory":
The reader should not get the
impression that the homotopy type of a
CW complex is determined by the number
of cells of each ...

**6**

votes

**1**answer

948 views

### Finding a cycle of fixed length in a bipartite graph

Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of ...

**5**

votes

**5**answers

1k views

### Let $G$ be a graph such that for all $u, v ∈ V (G)$, $u \ne v$, $|N (u) ∩ N (v )|$ is odd. Then show that the number of vertices in $G$ is odd

After working for sometime I figured out the following course of action. (from a few sample cases on 4 and 5 vertices)
i) I wanted to prove that the graph had no odd degree vertex.
ii) There exists ...

**10**

votes

**1**answer

726 views

### Counting colored rook configurations in the cube - when is it even?

Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...

**13**

votes

**1**answer

625 views

### Bipartite Nim-Geography

Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...

**72**

votes

**11**answers

51k views

### Sum of 'the first k' binomial coefficients for fixed n

I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...

**29**

votes

**4**answers

3k views

### How does this relationship between the Catalan numbers and SU(2) generalize?

This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.
As ...

**2**

votes

**2**answers

2k views

### Algorithmic aspects of maximizing a convex function over a convex set

Motivation
The problem I am facing can be considered a variant of the standard set packing problem. However; instead of being given a list of sets, I am given a function $\nu : 2^N \rightarrow \{0,1\}...

**12**

votes

**1**answer

1k views

### Combinatorial proof that large-girth graphs are sparse?

Theorem. Fix $\epsilon > 0$; for sufficiently large n, any graph with n vertices and $\epsilon \binom{n}{2}$ edges contains many (nondegenerate) cycles of length 4.
The proof is simple; put an ...

**4**

votes

**2**answers

806 views

### On the Bell Numbers

Edit (first version was incorrectly stated. Thank you Douglas and others for your corrections) Let $B_n$ be the $n$th Bell number (the number of partitions of a set with $n$ members). For each $n &...

**4**

votes

**2**answers

475 views

### Counting distinct undirected, partially labelled graphs

Suppose I have a hexagonal tile. Each edge can be connected to any subset of the other edges (including none). Connections are undirected, so a->b implies b->a, but they're not necessarily transitive -...

**36**

votes

**5**answers

3k views

### Factorials in Pascals Triangle

Hi,
I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are $\...

**38**

votes

**17**answers

10k views

### Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...

**4**

votes

**0**answers

158 views

### Coloring Cartesian Products with Constraints

Let $X$ and $Y$ be finite sets, and let $T_X$ (resp. $T_Y$) be a subset of the power set of $X$ (resp. of $Y$). (I think of the elements of $T_X$ as the tolerable subsets of $X$.)
A strict $(T_X,T_Y)...

**11**

votes

**0**answers

646 views

### A number theoretic identity

Let $n$ be a positive integer such that $2n+1$ is prime.
The elements of the factor group $G = \mathbb{F}^\times_{2n+1}/\{\pm 1\}$ can be represented by the integers $1,2,\ldots,n$. For every $x \in \...

**2**

votes

**1**answer

329 views

### Transitivity-related property of finite permutation groups

Let $\cal F$ denote the group of all finitely-supported permutations of $\mathbb N$.
Say that a finite subgroup $G$ of $\cal F$ is singular if $G$ acts transitively on
$\lbrace 1,2,3 \rbrace$ but ...

**4**

votes

**2**answers

1k views

### Polya Enumeration Formula with color indifference

Polya Enumeration Formula gives us 6 equivalence classes of 2-colorings of a square. But, in the Polya coloring, the following 2 colorings belong to 2 different equivalence classes:
...

**1**

vote

**1**answer

351 views

### Tournament formats

I'm looking for a format for a 4 vs. 4 tournament where the green team and blue team each has 6 players but two different people sit out each competition. How many match ups must occur before everyone ...

**20**

votes

**3**answers

994 views

### The probability for a sequence to have small partial sums

The question
Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that
$|a_1+a_2+\dots ...

**61**

votes

**7**answers

6k views

### Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...

**7**

votes

**4**answers

299 views

### How can I produce 'canonical' forms for rooted bipartite graphs?

The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the graph is bipartite, ...