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
2 votes
0 answers
54 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
2 votes
0 answers
253 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
275 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
153 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
151 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
76 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
139 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
1 answer
85 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
36 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
184 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
324 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,563
2 votes
0 answers
89 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
26 votes
0 answers
577 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
  • 361
1 vote
0 answers
65 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
332 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.9k
0 votes
1 answer
61 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
140 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,157
4 votes
0 answers
73 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
79 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
121 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
65 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
149 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
3 votes
1 answer
54 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
209 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
55 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
81 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,038
4 votes
0 answers
110 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.4k
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
213 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
217 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.8k
4 votes
0 answers
219 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
553 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
5 votes
1 answer
188 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
117 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
0 votes
0 answers
64 views

What is the complexity of computing isomorphism of two non-regular graphs?

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...
Eauriel's user avatar
0 votes
1 answer
40 views

Bounding maximum sum of integer matrix entries in a non-attacking rook placement

Let $A =(a_{ij})$ be a $m \times n$ matrix with nonnegative integer entries bounded above by $k$. To find the set of entries of $A$ in a non-attacking rook placement such that the sum $S$ of them is ...
JBuck's user avatar
  • 183
3 votes
0 answers
97 views

A class of bipartite graphs appearing in higher Auslander--Reiten theory

Let $G = (V,E)$ be a simple undirected bipartite graph with vertices $V$, edges $E$, and a chosen partition $V = X \cup Y$. Recall that the bipartite complement of $G$ is the graph on the same vertex ...
Isle of sand's user avatar
4 votes
1 answer
204 views

Double cover the edges of a complete graph by smaller complete graphs

Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
Wallace Rin's user avatar
0 votes
0 answers
59 views

Pairs of permutations such that $p(n)<2^k$ iff $n<2^k$

Let $p(n)$ be an arbitrary permutation of natural numbers such that $p(n)<2^k$ iff $n<2^k$. Let $q(n)$ be an inverse permutation of $p(n)$. Let $$ \ell(n)=\left\lfloor\log_2 n\right\rfloor $$ ...
Notamathematician's user avatar
1 vote
2 answers
243 views

Joint moments like $\tau(XYXYXY)$ in terms of individual moments of free variables $X,Y$

Terry Tao RMT book has the following formula for joint moment of freely independent random variables $X,Y$ in Section 2.5 $$\tau(XYXY)=\tau(X)^2\tau(Y^2)+\tau(X^2)\tau(Y)^2-\tau(X)^2\tau(Y)^2$$ ...
Yaroslav Bulatov's user avatar
3 votes
1 answer
191 views

Some questions about induced subgraphs of the directed hypercube graph

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
Agile_Eagle's user avatar
5 votes
0 answers
80 views

Formula and smallest solution for the A260711

Let $a(n)$ be A260711 without initial $0$ (i.e., numbers of the form $x^2 - y^2$ with $x > y$ where $x$ and $y$ are odd, $x + y$ is a power of $2$). The sequence begins with $$ 8, 16, 32, 48, 64, ...
Notamathematician's user avatar
4 votes
2 answers
274 views

Lower bounding a partition-related sum

We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
MikeG's user avatar
  • 665
5 votes
0 answers
77 views

Subspaces of $\mathbb{F}_2^N$ containing many pairs of far apart vectors

Let $S$ be a subset of vectors in $\mathbb{F}_2^{3n}$ having Hamming weight $n$. Suppose that $S$ contains $m$ pairs of vectors having disjoint supports (that is, they are at Hamming distance $2n$ ...
Kevin's user avatar
  • 530
4 votes
0 answers
189 views

Polynomials of growth for finite Heisenberg groups

Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes. For example for $H_3(Z/...
Mikhail Evseev's user avatar
2 votes
2 answers
73 views

Reference request for a subfamily of regular graphs

[Repost of same question math stack exchange which got no answers] I'm looking for literature on the following family of graphs: Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...
jojo's user avatar
  • 21
1 vote
1 answer
65 views

Multidimensional power series with coefficients equal to an order of stabilizer of a set of powers

I have encountered a necessity to work with a series of the following form. There are $N$ variables $x_1,\ldots x_N$. It is convenient to introduce monomial symmetric polynomials $m_{\lambda}$. They ...
V. Asnin's user avatar