Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

Maximal number of antichains of a strongly connected poset

Assume we have a strongly connected poset of $n$ elements, I am searching to know what is the maximal number of antichains such a poset can have? $2^n$ is obviously an upper bound, and my feeling is ...
7
votes
3answers
284 views

Changing combination lock

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new ...
2
votes
0answers
27 views

Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...
0
votes
0answers
64 views

Maximal “Spot It!” card count

This question was triggered by the game Spot It!. The game consists of cards, each having $k$ different symbols from an alphabet of $n>k$ symbols, with the property that any 2 cards have at least ...
2
votes
1answer
74 views

Bound for a combinatorial sum

I was playing around with a problem and I obtained a certain combinatorial sum. I was wondering if there was a way to simplify or bound it. I have a real valued function $f$, which satisfies $|f(x)| ...
23
votes
6answers
5k 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 ...
5
votes
4answers
219 views

Characterizing and counting boolean functions with all influences 1/2

Is there a characterization of boolean functions $f:\{-1,1\}^n \longrightarrow \{-1,1\}$, so that $\mathbf{Inf_i}[f]=\frac{1} {2}$, for all $1\leq i\leq n$? Is it known how many such functions there ...
4
votes
2answers
302 views

Can we sometimes define the parity of a set?

Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size ...
3
votes
0answers
67 views

Triangulations of special polyhedra

Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
2
votes
1answer
79 views

Looking for a canonical (matroid polytope) subdivision of the hypersimplex

A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...
0
votes
0answers
42 views

Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression: $\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left( 1-\theta \right) }\right) ^{m}}\left[ ...
2
votes
0answers
46 views

Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...
3
votes
1answer
95 views

Matching in the Boolean Algebra

We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show ...
4
votes
1answer
2k views

sum calculation

I would like to calculate, or bound from above, the following sum $$ \sum_{i=0}^n(n-2i)^p{p \choose i}, $$ here $p\geq 2$. Any references are very welcome. Thank you.
13
votes
0answers
488 views

What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such ...
0
votes
0answers
52 views

Computing a Levenshtein edit distance between two strings when a particular set of string edits is forbidden

Let's imagine we'd like to compute a Levenshtein edit distance between two strings, $S_1$ of length $n_1$ and $S_2$ or length $n_2$, consisting of characters over a finite alphabet $R$ of size $q$ ...
4
votes
2answers
123 views

Less general edge reconstruction problem for simple graphs

Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of ...
2
votes
1answer
114 views

Proof of existence of recursively inaccessible and Mahlo ordinals

As in title - I'm looking for a proof of the existence of a countable recursively inaccessible or recursively Mahlo ordinals, especially the first one. When looking for it in all the papers I stumbled ...
0
votes
0answers
87 views

Probability of differently loaded dice summing to a value [on hold]

I have a real world problem that boils down to the following: I'm playing dice. I have $n \approx o(10)$ differently biased die. The probability of the $i^{th}$ die showing $x_i$ is given by ...
6
votes
1answer
186 views

Under which constraints are there only finite numbers of irreducible eta product identities?

For the Dedekind eta function, defined as usual by $\eta(q) = q^{\frac1{24}} \prod\limits_{n=1}^{\infty} (1-q^{n})$, let for brevity $e_k:=\eta(q^k)$. An eta product identity (or eta identity for ...
1
vote
0answers
24 views

TSP: Approximation Ratio of the Double Tree Heuristic after Diagonals have been Removed

In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the ...
7
votes
1answer
145 views

What is the Essential Reason that allows a PTAS for the EUCLIDEAN TSP?

Questions: Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation ...
3
votes
1answer
149 views

Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature: The left color and ...
28
votes
1answer
3k views

An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
9
votes
3answers
1k views

Solving a general two-term combinatorial recurrence relation

What is known about explicit (not necessarily closed-form) solutions to the recurrence $$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$ with initial condition $R_0^0 = 1$ and ...
3
votes
1answer
89 views

Reference for Frobenius’s proof of Schur’s finite version of the Rogers - Ramanujan identities

In his paper “Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche” I. Schur has stated that Frobenius has communicated to him a simple direct proof of his finite version of the ...
0
votes
0answers
103 views

Error term in formula for products of necklaces

Let us consider the $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$, where the number of fixed necklaces of length n composed of a types of beads $N(n,a)$ can be calculated via totient function: ...
4
votes
1answer
235 views

Existence of a certain subset of natural numbers equidistributed modulo $m$ for every $m$

I was talking to a friend and the following set $S$ came up. Let $f$ be some real valued function tending to infinity. Let $S$ be a subset of natural numbers such that $|S \cap [1,N]| = N^{\delta}+ ...
3
votes
0answers
96 views

Asymptotics and combinatorics

Wright's expansion of $$ (1-z)^b\exp[A/(1-z)^c], \text{for } A > 0, 0<c<1\tag{1} $$ is, in the words of the late, great Mark Kac "well known to those that know it well". (See, for example, ...
1
vote
0answers
187 views

A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version: Randomly assign (with replacement) $N$ balls to $M$ urns. ...
4
votes
4answers
312 views

Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed. I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...
0
votes
0answers
36 views

Single element extensions of subspace arrangement over finite field

Matroids have single element extensions found by Crapo[2] to create ground set size $n+1$ matroids from ground set size $n$ matroids. Do subspace arrangements over a finite field $\mathbb{F}_q$ have ...
4
votes
1answer
86 views

Extremal graph theory for directed graphs

In extremal graph theory, there are results such as $$t(C_4,G)\geq t(K_2,G)^4,$$ where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...
-1
votes
0answers
29 views

departure time/overlap algorithm [closed]

i'm looking for "departure time/overlap algorithm" or any other idea. Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...
4
votes
1answer
751 views

Goin' with the flow with Kummer and Pascal: Combinatorics and geometry underlying the logarithm of the derivative operator

In a MO-Q111165 and associated MSE-Q125343, I present a pair of raising / lowering (creation / annihilation) operators $R_x = log(D)$ and $L_x = -x·D$ with $D=d/dx$ (for a sequence of functions ...
34
votes
6answers
2k views

Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here. Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
3
votes
2answers
357 views

battleship permutation

Consider the following one-dimensional version of the game battleships. There is a battleship somewhere on $\mathbb N$, i.e., a interval $N,\ldots,N+k$. Your task is to find whether this battleship ...
4
votes
1answer
100 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
2
votes
1answer
80 views

Computational complexity of deciding isomorphism of rational polyhedral cones

Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...
14
votes
1answer
1k views

What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...) Are there examples of results in "classical" [*] graph theory that have been achieved by using simplicial ...
12
votes
7answers
1k views

Cyclotomic Polynomials in Combinatorics

I am searching for a combinatorial significance of cyclotomic polynomials. The only examples I got are a paper by Neville Robbins http://www.emis.de/journals/INTEGERS/papers/a6/a6.pdf and two recent ...
0
votes
0answers
123 views

Conjecture relating differential equation and sum of a function over partitions

The following is an addition to A function from partitions to natural numbers - is it familiar?; the function $f(\lambda)$ as defined there, when summed over all partitions of n, gives an unexpected ...
50
votes
6answers
4k views

Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes: Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
3
votes
1answer
581 views

Big binary tree as an induced subgraph

I believe this is true: Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an induced subgraph which is a subdivision of a large binary tree or the line ...
2
votes
1answer
219 views

A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...
0
votes
1answer
252 views

Pros and cons of probability model for permutations

I am studying probability model of random permetuation Let $b(n; k)$ denote the number of permutations of {1,...,n} with precisely k inversions ($inv(\pi)$). The analytic approach was considered by ...
9
votes
3answers
496 views

In Szemerédi's Regularity Lemma, how many blocks are in the partition?

Suppose $G = (V,E)$ is a directed graph. For sets $A$ and $B$ of vertices of $G$, let $d(A,B) = |(A \times B) \cap E| / (|A||B|)$ denote the edge density between $A$ and $B$, and say that the pair ...
4
votes
5answers
491 views

A sum involving derivatives of Vandermonde

Consider the standard Vandermonde $V(x_1, \ldots, x_n) = \prod_{i < j} (x_i - x_j)$. I am intersted in the calculation of the following expression for fixed $k$: $$\sum_i (x_i)^k (d/dx_i)^k V(x_1 , ...
23
votes
1answer
1k views

There are n horses. At a time only k horse can run in the single race. How many minimum races are required to find the top m fastest horses?

There are n horses. At a time only k horse can run in the single race. How many minimum races are required to find the top m fastest horses? Please explain your answer. (There is no timer.) This was ...
1
vote
1answer
209 views

An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product ...