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
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$, ...

1
2 3 4 5
211