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,440 questions
16
votes
11answers
10k views
Different ways of proving that two sets are equal
I'm not sure if this is a soft question, or should be community wiki.
I was explaining to a student how to prove that two sets were equal using what I called the 'oldest trick in the book': to show ...
8
votes
2answers
778 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
2answers
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 ...
20
votes
4answers
22k 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
2answers
398 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
2answers
742 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 ...
16
votes
1answer
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
4answers
607 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
0answers
387 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
1answer
683 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
1answer
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 ...
21
votes
8answers
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
2answers
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
1answer
431 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
1answer
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
1answer
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
1answer
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
2answers
1k 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 ...
44
votes
2answers
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
1answer
898 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
1answer
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
3answers
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
2answers
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
2answers
552 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
6answers
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
4answers
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, ...
8
votes
2answers
727 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
3answers
666 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
3answers
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=...
7
votes
1answer
1k 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 ...
35
votes
6answers
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
4answers
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
1answer
222 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
2answers
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
1answer
683 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
4answers
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
3answers
1k 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 ...
40
votes
8answers
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
1answer
755 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
2answers
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 ...
34
votes
14answers
18k 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
1answer
357 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
1answer
282 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
1answer
308 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
0answers
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
3answers
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
5answers
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
1answer
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
1answer
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
3answers
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 ...