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,384
questions
1
vote
0
answers
15
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
151
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 ...
1
vote
0
answers
26
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
25
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 ...
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....
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 ...
-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 ...
2
votes
1
answer
207
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 ...
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$ ...
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 ...
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 $...
4
votes
1
answer
248
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|\...
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 ...
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 ...
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
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
3
votes
4
answers
292
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 ...
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 ...
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 ...
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$, ...
1
vote
0
answers
40
views
If $G$ is a connected bipartite graph, then the edge ideal $I(G)$ is normally torsion free
I am studying the paper "On the Ideal Theory of Graphs" by Simis, Vasconcelos and Villarreal, Journal of Algebra 167, No. 2, 389-416 (1994), MR1283294, Zbl 0816.13003. I got stuck at theorem ...
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, ...
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$. ...
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$. ...
4
votes
0
answers
70
views
Combinatorial interpretation of a pfaffian identity?
Let $n$ be a positive even integer. We introduce three types of skew-symmetric matrices, $A_{n+2}$, $B_n$ and $C_n$ (the subscript denotes the dimension of the matrices)
in terms of the variables $z_1,...
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 ...
5
votes
0
answers
116
views
If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?
Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
1
vote
1
answer
64
views
The sum of the signs of conjugacy classes in the symmetric group S_n [duplicate]
Let $r$ be the number of conjugacy classes of the symmetric group $S_n$ whose sign is $1$, i.e.
\begin{equation}
r := \#\{c \in \text{Conj} (S_n): \text{sgn} (c) = 1 \}.
\end{equation}
Let $s$ be the ...
6
votes
1
answer
143
views
Approximating distance on a finite graph with Hamming distance
For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, ...
1
vote
0
answers
33
views
Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?
I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
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).
...
5
votes
1
answer
205
views
Is the partition tiling relation transitive?
The following is motivated by an (as of yet) unanswered question on optimal colorings of graphs. I am convinced that the question below has a positive answer in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$, but ...
1
vote
0
answers
53
views
A question on generalized bases
I just came to know that it is possible to define a generalized base as an infinite sequence of natural numbers $\mathbf b=(b_1,b_2,\dots)$ where $b_i\ge 2$ for all $i$. With this definition, any $m\...
6
votes
0
answers
80
views
The meet of two dominant permutations in weak order of $S_n$
A permutation is called dominant if its Lehmer code is a partition, or equivalently if it avoids the pattern $132$.
I can prove that given a permutation $v\in S_n$, there is a unique dominant ...
4
votes
0
answers
104
views
Hyponontiling Wang tiles
Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling.
Is there a collection of at least 3 tiles that is not tiling, but such that after removing ...
3
votes
0
answers
103
views
Finite approximability of graphs with finitely many automorphisms
In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite.
Let $G = (V, E)$ be a graph. It is clear that any ...
3
votes
1
answer
211
views
How to find the coefficient of $x^k$ in the expression $\prod_{p=2}^n (1+xp) $
I got this general formula for $ n\in N$ (I showed it here)
$$\int_0^1 \left(\frac{x}{1-x} \ln x \right)^n dx=n \sum_{p=0}^{n-1}a(n,p+1) (-1)^{n-p} \zeta(p+2)+n! $$
where $a(n,k)$ is the coefficient ...
6
votes
1
answer
212
views
Fixed points for finitary distributive lattices bijection
Birkhoff's Fundamental Theorem of Finite Distributive Lattices says that there is a bijection
$$ \{ \textrm{finite posets}\} \to \{ \textrm{finite distributive lattices}\} $$
$$ P \mapsto J(P), $$
...
4
votes
0
answers
214
views
Optimal colorings
If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...
5
votes
2
answers
530
views
Representing natural numbers as sums of distinct prime powers
I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...
0
votes
0
answers
23
views
Algorithm of finding and counting cycles of varying lengths in dynamic or evolving graphs? [closed]
In this paper Alon, N., Yuster, R. & Zwick, U. Finding and counting given length cycles. Algorithmica 17, 209–223 (1997)., the authors present various methods for efficiently locating and tallying ...
5
votes
1
answer
185
views
Bijective proof for an identity concerning Stirling numbers of second kind
Let $\genfrac{\{}{\}}{0pt}{}{n}{k}$ the Stirling number of second kind, where $k$ is the number of parts in the partition.
If we take the identity that transforms the polynomial base $x^k$ into the ...
5
votes
1
answer
113
views
Identities for the generating functions of a sort of convolution powers of the Narayana numbers
Let $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers.
It satisfies $$\frac{1}{c(x)^k}+x^k c(x)^k=L_k(1,-x),$$
where $L_n(x,s)$ denote the Lucas polynomials defined by $...