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)

11
votes
0answers
316 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 ...
3
votes
2answers
99 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 ...
1
vote
1answer
94 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
69 views

Probability of differently loaded dice summing to a value

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
163 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
17 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
138 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
144 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
85 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
101 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
219 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
92 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
182 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. ...
3
votes
0answers
45 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
4answers
310 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
32 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 ...
3
votes
1answer
81 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
25 views

departure time/overlap algorithm [on hold]

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
719 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
97 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
78 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
121 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
218 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
251 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
494 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
485 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 ...
7
votes
4answers
280 views

Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...
2
votes
1answer
168 views

More asymptotics for trees

This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've ...
3
votes
2answers
271 views

Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge. Note that the number of cycles in $k$-necklace is at least $2^k.$ Question : Suppose a ...
1
vote
0answers
51 views

Bases of a matroid such that their complement is an independent set

Let $M$ be some matroid on $[n]$ with set of bases $\mathcal{B}$. I am interested in the subset $\mathcal{B}' \subseteq \mathcal{B}$ of bases $b \in \mathcal{B}$ with the property that $[n] \setminus ...
1
vote
1answer
123 views

Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...
27
votes
4answers
973 views

Stirling number identity via homology?

This is a question about the well-known formula involving both types of Stirling numbers: $\sum_{k=1}^{\infty}(-1)^{k}S(n,k)c(k,m)=0$, where $S(n,k)$ is the number of partitions of an $n$-element set ...
6
votes
1answer
228 views

Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$ p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; ...
4
votes
1answer
166 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let ...
6
votes
2answers
805 views

Erdos distance problem n=12

The recent paper On the Erdos distinct distance problem in the plane Authors: Larry Guth, Nets Hawk Katz prodded me to get a non-trivial example. Here is what I cannot find: an example of 12 ...
36
votes
6answers
3k views

Non-enumerative proof that there are many derangements?

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle ...
8
votes
3answers
269 views

A strengthening of Frankl's union-closed conjecture?

Frankl's union-closed conjecture states that if $F$ is a finite union-closed family of sets (i.e. a family that is closed under taking unions), then there must be an element that belongs to at least ...
51
votes
1answer
3k views

What is the amplituhedron?

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...
14
votes
3answers
798 views

Subposets of small Dushnik-Miller dimension

The Dushnik–Miller dimension of a partial order $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq_1},\ldots,{\leq_d}$ of total orderings of $P$ whose intersection is ${\leq}$, ...
4
votes
1answer
301 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...