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

7,289
questions

**8**

votes

**2**answers

875 views

### Local complementation in undirected graphs

Problem statement
Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in:
complementing the ...

**3**

votes

**2**answers

7k views

### Count of full, binary trees with fixed number of leaves

How many ways is there to build an arithmetic expression with fixed number of terms and fixed order? Let’s assume we have only one distinct operation that is neither commutative nor associative. The ...

**22**

votes

**4**answers

25k views

### Finding a cycle of fixed length

Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph?
All I know is that Alon, Yuster and Zwick use a technique called "color-coding",
which has a ...

**7**

votes

**2**answers

408 views

### Elements living in the conjugacy class and in the centralizer of an m-cycle in Am

Let m>1 be an odd natural number, x a m-cycle in Am, the alternating group in m letters, C the conjugacy class of x in Am.
Questiom: How can I describe the elements in the set { j | x^j in C} in ...

**13**

votes

**2**answers

750 views

### Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs?

We are interested in a solution to the following scheduling problem, or any information about how to find it or its existence. This one comes from real life, so you will not only be helping a ...

**18**

votes

**1**answer

1k views

### Is there a combinatorial proof of Cauchy-Schwarz?

I've only played with this a little for the past day or so, and haven't thought about it too hard, so it might be obvious. Obviously it's not fair to ask for a "combinatorial proof" of an inequality ...

**16**

votes

**4**answers

620 views

### Hamiltonian paths where the vertices are integer partitions

I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.
Let the vertices of the graph G=G(n) denote all the p(...

**2**

votes

**0**answers

392 views

### Is it always possible to choose two subsets with the same sum?

Given two positive integers $n, m$, let $A$ be a multiset of $n$ integers taken from { $ 1,2,\cdots, m$ }, and $B$ be a multiset of $m$ integers taken from { $1,2,\cdots,n$ }.
Is it always possible ...

**1**

vote

**1**answer

710 views

### Probability of n k-sided dice showing exactly m different faces

I found the following closed form solution for the abovementioned problem:
$${1\over k^n}\cdot{k!\over (k-m)!}\cdot{\{{n\over m}\}}$$ with ${\{{n\over m}\}}$ being the Stirling Number of the second ...

**8**

votes

**1**answer

4k views

### Defining “average rank” when not every ranking covers the whole set

Here's a mathematical modeling problem I came across while working on a hobby project.
I have a website that presents each visitor with a list of movie titles. The user has to rank them from most to ...

**22**

votes

**8**answers

2k views

### Cryptomorphisms

I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are
Topological Spaces. These can be defined in terms of open sets, ...

**35**

votes

**2**answers

1k views

### Is there a combinatorial reason that the (-1)st Catalan number is -1/2?

The $n$th Catalan number can be written in terms of factorials as
$$ C_n = {(2n)! \over (n+1)! n!}. $$
We can rewrite this in terms of gamma functions to define the Catalan numbers for complex $z$:
$$...

**4**

votes

**1**answer

445 views

### What interesting class of Matroids are there that contains the class of Gammoids?

I am looking for a (already-studied or interesting) class of Matroids such that
- Class of Gammoids are contained in it
One example would be Strongly-base-orderable Matroids. I would also be grateful ...

**11**

votes

**1**answer

2k views

### Topologies on an infinite symmetric group

Let $X$ be an infinite set, and let $G$ be the symmetric group on $X$. I want to understand $G$ by putting a topology on it, without imposing any more structure on $X$. What 'interesting' ...

**0**

votes

**1**answer

723 views

### Describe a tree by junctions

I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them).
These branches meet at certain points (junctions). Each junction is ...

**14**

votes

**1**answer

1k views

### Mathematical solution for a two-player single-suit trick taking game?

The question on games and mathematics that appeared recently on mathoverflow
(Which popular games are the most mathematical?)
reminded me of a problem I encountered some time ago : starting with the ...

**5**

votes

**2**answers

2k views

### General form of amount of triangles that can be formed in an MxN point lattice

I've been searching for the answer for many years, both by researching by myself and reading about the subject. Now I'm wondering if this has a solution.
The problem can be stated as follows.
Given ...

**45**

votes

**2**answers

3k views

### Collapsible group words

What is the length $f(n)$ of the shortest nontrivial group word $w_n$ in $x_1,\ldots,x_n$ that collapses to $1$ when we substitute $x_i=1$ for any $i$?
For example, $f(2)=4$, with the commutator $[...

**8**

votes

**1**answer

910 views

### Two [n] to [n] function families

Note. This question had a bounty, so at the end I accepted the best (and only) answer. However, a solution is implied by the answer to this question.
Question.
Fix n. We are interested in the biggest ...

**6**

votes

**1**answer

2k views

### Comparing number of spanning subgraphs

Hi all,
Let be $G_n=(V_n,E_n)$ a finite graph, where
$V_n= \{0,1,\ldots, n\} \times\{0,1,\ldots,n\}$
and $E_n\subset V_n^{(2)}$ is the edge set of the nearest neighbors in the $\ell^1$ norm, that ...

**14**

votes

**3**answers

2k views

### Markov chain on Groups

Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...

**2**

votes

**2**answers

2k views

### Hitting times for an N-dimensional random walk on a lattice with (strictly positive) random integer steps

Please consider a random walk on a finite N-dimensional lattice with vectors $(x_1, ..., x_N)$. We define the origin to be $(0, ..., 0)$ and the target to be at the point in the lattice furthest away ...

**6**

votes

**2**answers

563 views

### How many vertices of a polytope can be chopped off to produce a k-vertex facet?

Let P be a simple n-facet d-polytope with facet F, and let F have k vertices. Let H be a halfspace and Q be a simple (n-1)-facet polytope such that H ∩ Q = P.
In terms of k, what is an upper ...

**26**

votes

**6**answers

2k views

### Random Alternating Permutations

An alternating permutation of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5.
If $E_n$ is the number of ...

**16**

votes

**4**answers

2k views

### Checking if two graphs have the same universal cover

It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere.
You can define a notion of "covering graph" in graph theory, ...

**9**

votes

**2**answers

781 views

### Does a Cayley graph on a minimal symmetric set of generators determine a finite group up to isomorphism?

I suspect that the answer to my question is well-known to be no. To be more precise, let
$G$ and $H$ be nonisomorphic finite groups of the same order. Let $S \subseteq G$ and $T \subseteq H$ be ...

**13**

votes

**3**answers

703 views

### What bijection on permutations corresponds under RS to transpose?

The Robinson-Schensted correspondence is a bijection between elements of the symmetric group and ordered pairs of standard tableaux of the same shape.
Some simple operations on tableaux correspond to ...

**4**

votes

**3**answers

2k views

### Pigeonhole Principle for infinite case

Suppose $X_n$ are finite sets for any natural integer $n$. let $Y$ be an infinite subset of $\prod_n X_n$. Do there exist $y$ and $y'$ in $Y$ and an infinite subset $S$ of $\mathbb N$ such that $y_n=...

**9**

votes

**1**answer

2k views

### Jack polynomials as determinants

Jack symmetric polynomials are known to be generalizations of Schur functions $\chi_\lambda$, for which powerful Weyl determinant formulas are known.
Are there any generalizations of two determinant ...

**37**

votes

**6**answers

3k views

### Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian?

I'm looking for a "conceptual" explanation to the question in the title. The standard proofs that I've seen go as follows: use the Schubert cell decomposition to get a basis for cohomology and show ...

**30**

votes

**4**answers

2k views

### Tiling A Rectangle With A Hint of Magic

Here's a a famous problem:
If a rectangle $R$ is tiled by rectangles $T_i$ each of which has at least one integer sidelength, then the tiled rectangle $R$ has at least one integer side length.
$\...

**0**

votes

**1**answer

223 views

### Constructing a smooth lattice from a discrete one.

I have the standard lattice L defined over partitions of $1\ldots n$ under the split-merge relation. I also have an antimonotone function from L to R that's submodular, and so gives me a metric on L ...

**1**

vote

**2**answers

2k views

### Convert a confusion matrix to a distance/covariance matrix

Suppose I have a confusion matrix $A$ for a set of points: entry $i,j$ is the fraction of time over all $j$ (and similarly over all $i$) that when $i$ is present then $j$ is recognized (This means ...

**2**

votes

**1**answer

713 views

### Distance measure on weighted directed graphs

There is a simple and well-defined distance measure on weighted undirected graphs, namely the least sum of edge weights on any (simple) path between two vertices.
Can one devise a meaningful distance ...

**5**

votes

**4**answers

1k views

### Coloring Points in the Plane

Suppose one wants to color the points in the plane so any two points at distance one apart are different colors. How many colors are needed?
I heard this problem when I was a kid. Back then the most ...

**12**

votes

**3**answers

2k views

### Equivalence relations on permutations and pattern avoidance

I'm working on the interaction between equivalence relations on permutations and pattern avoidance. I've only considered Knuth equivalence and cyclic shifts until now and I'm looking for other ...

**41**

votes

**8**answers

4k views

### 1 rectangle <= 4 squares

Almost 25 years ago a professor at Indiana U showed me the following problem:
given a map $\mathbb{Z}^2\rightarrow\mathbb{R}$ such that the sum inside every square (parallel to the axes) is $\leq1$ ...

**13**

votes

**1**answer

764 views

### What does the incidence algebra of the lattices in C tell us about modular forms?

I have two different and probably unrelated questions that can both be superficially described by the title, so I hope you'll forgive me if I ask them together. They both fall under the category of ...

**7**

votes

**2**answers

337 views

### Wants: Polynomial Time Algorithm for Decomposing a Multiset of Rationals into Two Additive Subsets.

First, allow me to say that this problem was posed to me by a professor in the department. It is related to his research in a way that I do not know. However, since I couldn't come up with anything ...

**37**

votes

**14**answers

20k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...

**0**

votes

**1**answer

362 views

### Tetris in 3D with 5 units [closed]

Background: There are 7 "bricks" used in the game of Tetris. These are the 7 unique combinations of 4 unit squares in which every square shares at least one edge with another square. ("unique" in this ...

**4**

votes

**1**answer

289 views

### Origin of Fujimura set

If we have 10 coins arranged in an equilateral triangle and we want to know the minimum number of coins we can remove so that none of the remaining coins form an equilateral triangle the remaining ...

**6**

votes

**1**answer

309 views

### Sparse approximate representation of a collection of vectors

Suppose I have a collection of $n$ vectors $C \subset \mathbb{F}_2^n$. They are of course spanned by the canonical set of $n$ basis vectors.
What I would like to find is a much smaller (~ $\log n$) ...

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

831 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 constant ?
Some remarks :
If ...

**26**

votes

**5**answers

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

530 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

846 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}[ \...