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

**5**

votes

**0**answers

464 views

### Consensus clustering using set union

Problem statement
Let $P$, $Q$ and $R$ be three partitions into $p$ nonempty parts (denoted by $P_h$'s, $Q_i$'s and $R_j$'s) of the set {$1,2,\ldots,n$}. Find two permutations $\pi$ and $\sigma$ that ...

**13**

votes

**3**answers

770 views

### Orthogonal matrices with small entries

Is it true that for any $n$, there exists a $n \times n$ real orthogonal matrix with all coefficients bounded (in absolute value) by $C/\sqrt{n}$, $C$ being an absolute contant ?
Some remarks :
If ...

**24**

votes

**5**answers

6k views

### Erdos Conjecture on arithmetic progressions

Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...

**10**

votes

**1**answer

502 views

### Condition for existence of certain lattice points on polytopes

Let $a_1,\cdots, a_n$ be integers such that $a_i\geq 2$ for all $i$ and $k>0$ another integer.
I am interested in whether there exist integers $x_1,\cdots, x_n$ with $0<x_i<a_i$ satisfying:
...

**15**

votes

**1**answer

1k views

### How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges?

I would like to know the asymptotic number of labelled disconnected (simple) graphs with n vertices and $\lfloor \frac 12{n\choose 2}\rfloor$ edges.

**8**

votes

**3**answers

1k views

### Weighted Regular Graphs

The following graph theoretic notion appeared in an economics paper entitled: "Prize competition under limited comparability, by Michele Piccione and Ran Spiegler which studies models of economics ...

**3**

votes

**1**answer

836 views

### How to choose $L$ size-$m$ subsets of $\{1,\ldots,n\}$ to maximize expected max overlap with another randomly chosen subset?

GIVEN: Positive integers $n,m,L$ and probabilities $p_1, p_2, \ldots, p_n$.
GOAL: Choose $L$ size-$m$ subsets $S_1, S_2, \ldots, S_L$ of $\{1,2,\ldots,n\}$ to maximize $\displaystyle \mathbb{E}[ \...

**11**

votes

**1**answer

500 views

### Does a triangulation without fixed simplex property always exist?

Suppose we are given a triangulable topological space $X$. If $X$ has the fixed point property (FPP), then obviously for every triangulation $K$ of $X$ and every simplicial map $f:K\to K$ a simplex $\...

**20**

votes

**6**answers

1k views

### Combinatorial sequences whose ratios $a_{n+1}/a_{n}$ are integers

I have a proof technique in search of examples. I'm looking for combinatorially meaningful sequences $\{a_n\}$ so that $a_{n+1}/a_n$ is known or conjectured to be an integer, such that there is a ...

**8**

votes

**2**answers

211 views

### Flipping Hilbert series of semigroup rings

I'll first give intuition, and then give a precise statement.
For $|z|<1$, we have $\sum_{i \geq 0} z^i = 1/(1-z)$. For $|z|>1$, we have $\sum_{i<0} (-1) z^i=1/(1-z)$. Thus, the two ...

**3**

votes

**3**answers

546 views

### Average distance between numbers of the form $2^{a}3^{b}$

I want to order all numbers of the form $2^a3^b$. I need to find the average distance between a random consecutive pair.
For example, in case of a random consecutive pair $2^{n'}$ and $2^{n'+1}$, the ...

**4**

votes

**1**answer

1k views

### Combinatorics journals processing time

This is a spin-off question from How to select a journal?. Is there is any data available regarding processing time (acceptance time, time from submission to publication, or similar) specifically for ...

**35**

votes

**6**answers

10k views

### Submitting to arXiv when unaffiliated

I am writing a short paper in the area of combinatorics.
When the paper is complete, I would like to be able to submit it to arXiv.
The reasons that I would like to submit to arXiv are:
To obtain a ...

**0**

votes

**2**answers

504 views

**8**

votes

**1**answer

450 views

### devise a joint distribution of $\alpha$ and $\beta$

If we assume probability density distribution functions of random variables $\alpha$, $\beta$ and $\alpha/ \beta$, we would like to devise a joint distribution of $\alpha$ and $\beta$. Although ...

**34**

votes

**7**answers

4k views

### Help with a double sum, please

Here is a double series I have been having trouble evaluating:
$$S=\sum_{k=0}^{m}\sum_{j=0}^{k+m-1}(-1)^{k}{m \choose k}\frac{[2(k+m)]!}{(k+m)!^{2}}\frac{(k-j+m)!^{2}}{(k-j+m)[2(k-j+m)]!}\frac{1}{2^{k+...

**2**

votes

**1**answer

182 views

### Polytopes related to the conjugation action of a Lie group on multiple copies of itself?

Let G be a finite dimensional real Lie group. As I understand it, the quotient space of G acting on itself by conjugation is a well studied polytope which can be identified with the fundamental alcove ...

**9**

votes

**2**answers

1k views

### A generalization of Boolean matrix multiplication for order-3 tensors

The Boolean matrix product of two 0-1 $n \times n$ matrices $A$ and $B$ is the matrix $C$ defined as
$$C[i,j] = \vee_{k=1}^n (A[i,k] \wedge B[k,j]).$$ If $A = B$ and the matrix is an adjacency matrix ...

**18**

votes

**2**answers

1k views

### Deligne-Simpson problem in the symmetric group

Question.
Let $C_1,\dots,C_k$ be conjugacy classes in the symmetric group $S_n$. (More explicitly,
each $C_i$ is given by a partition of $n$; $C_i$ consists of permutations whose cycles
have the ...

**-1**

votes

**1**answer

445 views

### cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]

Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that |Q(B)...

**3**

votes

**3**answers

416 views

### Uniqueness of a polygon

Suppose I have two $n$-sided polygons A and B. Is there a non-trivial upper bound on the number of parameters (eg. area, perimeter, etc) of the two polygons, that need to be the same, for A and B to ...

**10**

votes

**2**answers

830 views

### Canonical bases for modules over the ring of symmetric polynomials

The ring $S=\mathbb{C}[x_1,x_2,\dots,x_n]^{S_n}$ of symmetric polynomials has a number of commonly used bases, but the undisputed world champion of these is the basis consisting of Schur polynomials $...

**21**

votes

**1**answer

1k views

### Red-blue alternating paths

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where $V_k=\{v_1,\ldots,v_k\...

**4**

votes

**6**answers

682 views

### Reconstructing an ordering of a multiset from its consecutive submultisets

We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...

**18**

votes

**10**answers

4k views

### Applications of infinite Ramsey's Theorem (on N)?

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...

**8**

votes

**3**answers

2k views

### Balls in boxes (partition)

Given 100 boxes. Each contains arbitrary number of red, blue and green balls, i.e., 100 non-negative integer triples $(r_i,b_i,g_i)$.
Prove it's always possible to find 51 boxes so that the total ...

**8**

votes

**2**answers

600 views

### Enumeration of graphs arising in invariant theory

I've been working on a talk based on some stuff in Olver's "Classical Invariant Theory" book and have been wondering about a related graph enumeration problem.
Start with a triple $(n,v,e)$ of ...

**13**

votes

**2**answers

611 views

### Archaeogenetics

This question is meant to be applied to recover historic information from genetic data.
The following model, is (probably) the simplest possible which takes recombinations into account.
First, let ...

**4**

votes

**2**answers

769 views

### How many n×n (0,1)-matrices with row/column sum 4 and trace 0 are there?

(asked by Shanzhen Gao, shanzhengao at yahoo.com, on the Q&A board at JMM)
Is there a closed formula for the number of n×n (0,1)-matrices with column sum 4, row sum 4, and trace 0?

**2**

votes

**1**answer

1k views

### About the Shannon Switching Game

I was playing around with the Shannon Switching Game for some planar graphs, trying to get some intuition for the strategy, when I noticed a pattern. Since I only played on planar graphs, I'll ...

**5**

votes

**1**answer

957 views

### Gamma function versions of combinatorial identites?

We can extend the binomial coefficient $\binom{n}{k}$ to $\mathbb{R}$ or $\mathbb{C}$ by defining $\binom{x}{y}=\frac{\Gamma(x+1)}{\Gamma(y+1)\Gamma(x-y+1)}$. Do any the standard binomial coefficient ...

**12**

votes

**4**answers

2k views

### Representing numbers in a non-integer base with few (but possibly negative) nonzero digits

Background
In a recent question about Fibonacci numbers, it was claimed that
every integer can be written in the form $\sum_{i=1}^6 \epsilon_i F_{n_i}$ with $\epsilon_i \in \{0,-1,1\}$. The upper ...

**1**

vote

**1**answer

769 views

### fibonacci identity using generating function

There are many nice ways of showing that $f_0^2+f_1^2+\cdots+f_n^2=f_{n+1}f_n$. I was wondering if there is a way of showing this using the generating function $F(x)=\frac{1}{1-x-x^2}=\sum_{i\geq0}...

**42**

votes

**15**answers

8k views

### Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication
"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."
for ...

**2**

votes

**3**answers

247 views

### optimizing Frobenius instance solutions

The papers I've found about the Frobenius instance problem (given a set of distinct positive integers, find the positive integer coefficients that make a linear combination of some of them add up to a ...

**4**

votes

**2**answers

283 views

### Finding the codomain of a monoid homomorphism

We have a monoid M, and a function $f: M \rightarrow \{0, 1\}$. We're promised that this function factors through a (surjective) homomorphism to a finite abelian group (considered as a commutative ...

**10**

votes

**2**answers

2k views

### Algorithm for decomposing permutations

Is there an algorithm for solving the following problem: let $g_1,\ldots,g_n$ be permutations in some (large) symmetric group, and $g$ be a permutation that is known to be in the subgroup generated by ...

**25**

votes

**3**answers

9k views

### Cutting a rectangle into an odd number of congruent pieces

We are interested in tiling a rectangle with copies of single tile (rotations and reflexions are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.
What happens when ...

**22**

votes

**5**answers

3k views

### Complete graph invariants?

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a ...

**15**

votes

**1**answer

809 views

### Are there analogues of Desargues and Pappus for block designs?

Finite projective planes are fascinating objects from many perspectives. In addition to the geometric view, they can be viewed as combinatorial block designs.
From the geometric perspective, there ...

**6**

votes

**3**answers

437 views

### A quadratic form

Let $q$ be a power of 2. Let $P$ be the set of polynomials in
$F_q [x]$ of degree d or less.
Let $\mathbb{Z}$ be the ring of integers. For any $f \in P$, let $\psi(f)$ be the
number of distinct ...

**12**

votes

**1**answer

1k views

### Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

Consider functions on the discrete cube $\{-1,1\}^n$.
We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of co-...

**6**

votes

**2**answers

1k views

### Yet another graph invariant: the similarity matrix

Preliminaries
Let $n \in \mathbb{N}$ and $v$ be a vertex of a graph $G$. Let the $n$-neighbourhood of $v$, $N_n(v)$, be the induced subgraph of $G$ containing $v$ and all vertices at most $n$ edges ...

**68**

votes

**10**answers

15k views

### Does War have infinite expected length?

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.
The ...

**17**

votes

**1**answer

697 views

### Balancing problem

There was a problem in an Olympiad selection test, which went as follows: Consider the set $\{1,2,\dots,3n \}$ and partition it into three sets A, B and C of size n each. Then, show that there exist x,...

**10**

votes

**1**answer

702 views

### Which lattices have more than one minimal periodic coloring?

The lattice $\mathbb{Z}^n$ has an essentially unique (up to permutation) minimal periodic coloring for all $n$, namely the "checkerboard" 2-coloring. Here a coloring of a lattice $L$ is a coloring of ...

**12**

votes

**1**answer

3k views

### Collection of subsets closed under union and intersection

Suppose A is a set and S is a collection of subsets closed under arbitrary unions and intersections. Can we find a collection F of functions from A to itself such that a subset B of A is in S if and ...

**9**

votes

**5**answers

842 views

### What's the name of graphs with each vertex contained in a cycle?

A tree is a graph with no vertex contained in a cycle.
A non-tree is a graph with some vertex contained in a cyle.
What's the name of graphs with each
vertex contained in a cycle?

**3**

votes

**1**answer

457 views

### Do all correlation coefficients induce a pseudometric?

The Kendall tau distance was originally defined as a correlation coefficient. It seems clear to me that every metric function $d$ that is bounded by $b$, induces a correlation coefficient. That is:
...

**13**

votes

**5**answers

1k views

### Asymptotics of a Bernoulli-number-like function

Tony Lezard asked me the following question which seemed like it should not be too hard but which I did not immediately see how to answer. Define $f(n,k)$ recursively by $f(1,k) = 1$ and
$$f(n,k) = \...