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.

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 ...
3
votes
1answer
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
1answer
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
6answers
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
2answers
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
3answers
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
1answer
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
6answers
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
2answers
504 views

Is a lattice of convex sets distributive?

Is a lattice of convex sets in $R^2$ distributive?
8
votes
1answer
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
7answers
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
1answer
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
2answers
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
2answers
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
1answer
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
3answers
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
2answers
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
1answer
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
6answers
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
10answers
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
3answers
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
2answers
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
2answers
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
2answers
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
1answer
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
1answer
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
4answers
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
1answer
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
15answers
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
3answers
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
2answers
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
2answers
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
3answers
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
5answers
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
1answer
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
3answers
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
1answer
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
2answers
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
10answers
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
1answer
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
1answer
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
1answer
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
5answers
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
1answer
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
5answers
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) = \...