Stack Exchange Network

Stack Exchange network consists of 175 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.

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