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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
19 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 ...
Anthony's user avatar
  • 31
0 votes
0 answers
10 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 ...
Joseph Zambrano's user avatar
0 votes
0 answers
18 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 ...
bc a's user avatar
  • 41
4 votes
0 answers
89 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. ...
Alexander Chervov's user avatar
2 votes
0 answers
61 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....
Alexander Chervov's user avatar
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 ...
Matt Samuel's user avatar
  • 2,008
-3 votes
0 answers
48 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 ...
Zappa's user avatar
  • 1
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 ...
ABIM's user avatar
  • 5,019
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$ ...
bernardorim's user avatar
0 votes
0 answers
33 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 ...
Notamathematician's user avatar
1 vote
0 answers
190 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 $...
Sayan Dutta's user avatar
4 votes
1 answer
243 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|\...
bc a's user avatar
  • 41
3 votes
0 answers
135 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 ...
Alexander Chervov's user avatar
1 vote
1 answer
137 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 ...
Dominic van der Zypen's user avatar
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) ...
Mazen Saaed's user avatar
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 ...
Makenzie's user avatar
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 ...
Connor. Y. X. Liu's user avatar
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 ...
anonymous's user avatar
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 ...
Will's user avatar
  • 105
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 ...
mashedcarrots's user avatar
2 votes
1 answer
173 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 ...
Ood's user avatar
  • 121
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 ...
Kuzja's user avatar
  • 101
3 votes
4 answers
253 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 ...
Martin Rubey's user avatar
  • 5,533
-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-...
jables's user avatar
  • 1
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 ...
Mikhail Borovoi's user avatar
25 votes
0 answers
539 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 ...
M.Monet's user avatar
  • 351
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$, ...
Sophie M's user avatar
  • 675
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 ...
Sowbarnika R's user avatar
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, ...
Taras Banakh's user avatar
  • 40.8k
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$. ...
Guoqing's user avatar
  • 431
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$. ...
YHBKJ's user avatar
  • 3,127
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,...
eddy ardonne's user avatar
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 ...
Pritam Majumder's user avatar
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 ...
Per Alexandersson's user avatar
1 vote
1 answer
63 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 ...
alpha2357alpha's user avatar
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, ...
David Gao's user avatar
  • 1,262
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 ...
Siddhu Neehal's user avatar
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). ...
Stéphane Laurent's user avatar
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 ...
Dominic van der Zypen's user avatar
1 vote
0 answers
52 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\...
Dumbest person on earth's user avatar
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 ...
Matt Samuel's user avatar
  • 2,008
4 votes
0 answers
103 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 ...
domotorp's user avatar
  • 18.3k
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 ...
David Gao's user avatar
  • 1,262
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 ...
Faoler's user avatar
  • 431
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), $$ ...
Sam Hopkins's user avatar
  • 22.7k
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) \...
Dominic van der Zypen's user avatar
5 votes
2 answers
529 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 ...
Marcos Cramer's user avatar
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 ...
138 Aspen's user avatar
  • 133
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 ...
Johnny Cage's user avatar
  • 1,543
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 $...
Johann Cigler's user avatar

1
2 3 4 5
208