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.
10,516
questions
0
votes
0
answers
3
views
Covering base sets $X$ with a subset family satisfying a "partial covering property"
Let $X$ be an $n$ element base set. Suppose I have a subset family $\mathscr{F} \subset 2^X$ satisfying the following property:
(*) For any subset $Y \subset X$, we can find an element $F \in \mathscr{...
0
votes
1
answer
129
views
Decomposition of identity
Fix an integer $n$ and consider a finite numbers $m$ of subsets $ S_i \subset [n]$ such that $$ \bigcup_{i = 1}^m S_i = [n].$$ Do we have a necessary and sufficient condition on the subsets $S_i$ so ...
3
votes
4
answers
288
views
Bijections on the set of integer partitions of $n$
I am looking for natural bijections from the set of integer partitions
of $n$ to itself. Of course, I have no definition of natural, but for
the purpose of this question it suffices that it appears ...
1
vote
0
answers
23
views
Structural description of a particular set motivated by graph reconstruction
$\DeclareMathOperator\Coh{Coh}\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Aut{Aut}$In this post, I asked a question regarding a particular function $\psi$ whose construction is motivated by the ...
0
votes
0
answers
24
views
Does this "linear-approximated" version of Graph Counting Lemma hold?
Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
1
vote
3
answers
5k
views
Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?
I am not expertise in graph theory. So have to ask this question here. The term "good" means that the algorithms should be efficient for general undirected simple connected graphs with a higher ...
1
vote
0
answers
192
views
On $(k,\ell)$-sumfree sets
Call a set $\mathcal S \subset \mathbb N$ to be $(k,\ell)$-sumfree if there are no non-trivial solutions to the equation
$$x_1+\dots +x_k = y_1+\dots +y_\ell$$
in the set (for distinct $x_i$'s and $...
12
votes
3
answers
2k
views
How to efficiently sample uniformly from the set of $p$-partitions of an $n$-set?
Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?
3
votes
1
answer
355
views
Ask for a generating function or an explicit expression of a triangle of positive integers
Preliminaries
I encountered the following triangle of positive integers:
$c_{n,k}$
$n=1$
$n=2$
$n=3$
$n=4$
$n=5$
$n=6$
$n=7$
$n=8$
$k=0$
$1$
$3$
$15$
$105$
$315$
$3465$
$45045$
$45045$
$k=1$
$5$
$...
12
votes
1
answer
2k
views
Hobbled rook tour – Hamiltonian cycle on square grid
Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
4
votes
0
answers
90
views
Does the permutohedron satisfy any minimal distortion property for graph metric vs Euclidean distance?
We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. ...
2
votes
0
answers
62
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
1
vote
4
answers
1k
views
Covering of a graph via independent sets
I suspect that a topic such as this may have been considered before: if so, I hope that someone can point me to a reference on the subject.
I have a graph G with an upper bound d on its maximum ...
2
votes
1
answer
206
views
Order on Euclidean space in which a finite poset embeds
Fix positive integers $k$ and $n$.
For which finite posets $(X,\lesssim)$ with $\#X=k$ does there exist an order embedding $\phi\colon(X,\lesssim)\to (\mathbb{R}^n,\le)$, where $\le$ is the standard ...
3
votes
0
answers
65
views
Expansion of Schubert polynomials into standard elementary monomials
I have an explicit formula for expressing any Schubert polynomial in terms of standard elementary monomials that may or may not be cancelation-free. I haven't determined this yet, but it seems likely ...
1
vote
1
answer
138
views
Permutation graph with insert-and-shift
Motivation. I am working with a database software that allows
you to sort the fields of any given table in the following
peculiar way. Suppose your fields are numbered $1,\ldots, 18$.
Next to every ...
-3
votes
0
answers
50
views
Bijective proof that kC(n,k)=nC(n-1,k-1) [closed]
I have an exercise that I tried and I really can't do it I'm completely stuck, so I have to prove the equality kC(n,k)=nC(n-1,k-1) with A BIJECTIVE PROOF so by finding two sets as well as a bijection ...
7
votes
1
answer
364
views
What is this Ramsey problem?
Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
2
votes
0
answers
48
views
How many ways to win a game between two teams with arbitrary player skills
Suppose we have $n\geq 4$ players $p_1,\cdots,p_n$ of a game between two teams: team $A$ and team $B$ (disjoint sets, each with two or more players, so that $|A|+|B|=n$). Assume that each player $p_i$ ...
4
votes
1
answer
247
views
A question related to "Locally Sidorenko" type problem
Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant.
Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...
0
votes
0
answers
34
views
Permutation for the fast computing of the $k$-th partition of $n$ in reverse lexicographic order
Let $a(n)$ be A000041 (i.e., $a(n)$ is the number of partitions of $n$ (the partition numbers)).
Let $b(n)$ be A000070. Here
$$
b(n) = \sum\limits_{i=0}^{n}a(i)
$$
Let $c(n)$ be $k-1$ where $k$ is the ...
4
votes
4
answers
2k
views
Homotopical Combinatorics
I have a question about the situation of homotopical combinatorics. There are many topics about combinatorial homotopy. But, I can't find any topic about homotopical combinatorics.
More precisely, are ...
3
votes
0
answers
137
views
What d.o. $\sum_i f_i(z)\partial_z^i$ correspond to subalgebras $M$ in polynoms $C[x_i]$ being Langlands dual to motive of $Spec(M) \to X$?
Briefly: The question is about presenting explicit examples of the construction discussed in the recent MO question "Relation between motives and geometric Langlands" and Will Sawin's asnwer ...
0
votes
1
answer
131
views
Formula for partitions of integers with no subpartition being a partition of $t$
When it comes to partitions, I know we can impose some modest restrictions (maybe even a couple) on the partitions and obtain counting formula, but I would like to impose some more serious constraints ...
0
votes
1
answer
73
views
Number of regions created by r hyper-planes in n-dimensional space [closed]
I found this formula for calculating maximum number of regions created by r hyper-planes in n-dimensional space (n<=r)
...
0
votes
0
answers
101
views
Unimodality of the Stirling numbers
For fix $n$, the (unsigned) Stirling number of the first kind $c(n,k)$ and the Stirling number of the second kind $S(n,k)$ are both unimodal.
Erdős Paul proved the sequence $c(n,k)$ has a unique mode ...
9
votes
2
answers
911
views
Realization space of matroids
Let $M$ be a matroid admitting a coordinatization over a complex vector space. If we know that the complex coordinatization space for $M$ is connected, then may we conclude that the matroid admits a ...
0
votes
1
answer
80
views
Homology of independence complex after removing a vertex
Let $G$ be a chordal graph, $I(G)$ be its independence complex, and $v \in V(G)$ be a simplicial vertex (that is, $v$'s neighborhood is a clique).
Is there a way to relate the homology of $I(G)$ and ...
0
votes
0
answers
87
views
How would i prove that the final number in a gamed list is even? [closed]
Let’s play a game. We start with a list of numbers 1, 2, 3, . . . , 2024. We take turns by picking two numbers from the list, say a and b, and removing them. Then, we insert exactly one of the numbers ...
2
votes
1
answer
174
views
Generating all possible subsets in order of sum
Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...
8
votes
1
answer
195
views
Length of optimal play in Hex as a function of size
Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...
2
votes
1
answer
167
views
Tighter lower bound of the lower triangular sum of an arbitrary Latin square
In this math.stackexchange.com question I seek a tighter bound than the one I presented in there in the question. Rob Pratt puts forth a conjecture in his answer motivated by the dual problem of the ...
0
votes
2
answers
73
views
Isometric path cover number of the 2 dimensional grid graph
I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
0
votes
0
answers
88
views
How many possible Venn diagrams are there for given cardinalities of the sets?
Consider $n$ non-empty finite sets with cardinalities $c_1$, $\ldots$, $c_n$. How many possibilities are there for the Venn diagram of these sets? (I'm surprised I didn't find the answer with Google).
...
3
votes
0
answers
31
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
4
votes
1
answer
204
views
Diameter of the "Masterball-puzzle" permutation groups by a kind of Cartier-Foata enumeration?
There is an wonderful blog post by Jordan S. Ellenberg SHOULD YOU BE SURPRISED BY THE DIAMETER OF THE NXNXN RUBIK’S GROUP?. Which explains how one can come to $N^2log(N)$ estimate of the diameter of ...
0
votes
0
answers
30
views
Asymptotic bound on the number of simple connected graphs of bounded degree
I have posted this question on Mathematics, but unfortunately no luck so far.
Let $\mathcal{G}$ be the family of simple connected graphs on $n$ vertices, where each graph has more than $m$ edges, and ...
-1
votes
0
answers
52
views
A Near Closed-Form Expression of Strict Partition Function Inquiry [closed]
I am an independent researcher working in various fields of mathematics and sciences. I am working on a strict partition problem. I believe I have found a very fast exact solution that is a near-...
25
votes
0
answers
540
views
A conjecture about inclusion–exclusion
$\newcommand\calF{\mathcal{F}}
\def\cupdot {\stackrel{\bullet}{\cup}}
\def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
2
votes
0
answers
83
views
Estimating the cardinality of the set of conjugacy classes of subgroups in a finite group of given order
1. Let $G$ be a finite group of order $n$. I need an estimate for the number $c$ of conjugacy classes of subgroups $D\subseteq G$.
Note that any subgroup of $G$ contains $1_G$, and so the set of all ...
9
votes
1
answer
663
views
Sufficient condition for linear separability of a boolean function on $n$ variables
This is a cross-post of two recent questions at math.stackexchange without answers: Q1 and Q2.
A boolean function on an $n$-dimensional hypercube is linearly separable when the convex hulls of the ...
0
votes
1
answer
118
views
The generating series of the weighted species of fixpoints
I am wondering if the series
$$\sum_{n=0}^\infty \left(\sum_{k=0}^n \frac{D_{n-k}}{k!(n-k)!}t^k\right)X^n$$
where $D_m$ is the number of derangements of $m$ letters, admits a representation in closed ...
9
votes
1
answer
327
views
Is the group of translations of an affine plane always commutative?
$\DeclareMathOperator\Dil{Dil}\DeclareMathOperator\Trans{Trans}\DeclareMathOperator\Col{Col}$An affine plane is a set of points $X$ endowed with a family $\mathcal L$ of subsets of $X$, called lines, ...
7
votes
1
answer
385
views
Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history
Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces.
Counting the ...
0
votes
1
answer
57
views
Given $F[N,M]=\sum_{m=0}^{N-1}(-1)^{N-1-m}(m+1)^M)/(m!(N-1-m)!)$, show $F[N,N-1]=1$ and $F[N,M]=0$ for $M<N-1$ [closed]
The function defined by
$$
F[N,M]=\sum_{m=0}^{N-1}\frac{(-1)^{N-1-m}(m+1)^M}{m!(N-1-m)!}
$$
where $N,M$ are positive integers. I want to show
$$
F[N,N-1]=1,\ F[N,M]=0
$$
for $N>2$ and $M<N-1$. ...
11
votes
1
answer
372
views
Does every finite affine plane have the doubling property?
Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms:
Any distinct points $x,y\...
5
votes
5
answers
545
views
Is every uniform hyperbolic linear space infinite?
I start with definitions.
Definition 1. A linear space is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ satisfying three axioms:
(L1) for any distinct ...
2
votes
1
answer
95
views
Is every Cartesian biaffine plane affine?
This question concerns the (synthetic) geometry of linear spaces.
Definition 1. A linear space is a pair $(P,\mathcal L)$ consisting of a set $P$ whose elements are called points and a family $\...
2
votes
1
answer
130
views
Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?
Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...
1
vote
0
answers
64
views
Tuples of natural numbers with no mutual divisibility and large reciprocal sums
Standard apology in case this is something simple, as I'm not a number theorist.
Let $E_1, \dots, E_n$ be disjoint finite sets of natural numbers, such that for any $a_1 \in E_1, \dots, a_n \in E_n$, ...