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
7
votes
0answers
236 views

When does a graph have a minimally strong orientation?

Given any asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly ...
0
votes
0answers
8 views

Bound on the number of unlabeled tree on n vertices

By the Cayley's Theorem, the number of labeled tree on n vertices is at most n^{n-2}. On the other hand, what is the bound on the number of unlabeled tree on n vertices?
14
votes
7answers
2k views

A special type of generating function for Fibonacci

Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$. Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them: $$\...
0
votes
0answers
49 views

About a generalization of complete graphs

Does anyone know what are called (if there is any nomenclature for this class of graphs in the literature) the connected graphs such that each of their edge belongs to some triangle? For example, ...
0
votes
0answers
15 views

Additive graph/digraph invariants $f$ and $g$ such that if $f(G)=\min(g(D):D\text{ is an orientation of }G)$ then $f(G)=\min(f(G/uv),f(G+uv))$

If we let $\rho(D)$ be the number of arcs in any digraph $D$ minus the number of arcs in any minimum equivalent subdigraph of $D$, then for every $2$-edge connected graph $G$, is it true for all $u,v\...
1
vote
0answers
47 views

Does there exist a subset $E \in \mathbb{Z}_{p^2}^4$ such that $\Pi(E) \neq \mathbb{Z}_p$?

Denote $\mathbb{Z}_{p^2}$ be the ring residues modulo $p^2,$ i.e $$ \mathbb{Z}_{p^2} = \left\{ 0,1,2,\dots, p^2-1\right\}.$$ $$\mathbb{Z}_{p^2}^{d} = \underbrace{\mathbb{Z}_{p^2} \times \dots \times ...
17
votes
3answers
722 views

Cyclic action on Kreweras walks

A Kreweras walk of length $3n$ is a word consisting of $n$ $A$'s, $n$ $B$'s, and $n$ $C$'s such that in any prefix there are at least as many $A$'s as $B$'s, and at least as many $A$'s as $C$'s. For ...
5
votes
4answers
313 views

Request for an exact formula related to a partition in number theory

The Frobenius equation is the Diophantine equation $$ a_1 x_1+\dots+a_n x_n=b,$$ where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$ must consist of non-...
20
votes
1answer
570 views

To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $P$ satisfies: ...
4
votes
2answers
388 views

What generalizes symmetric polynomials to other finite groups?

Multivariate polynomial indexed by ${1, \ldots, n}$ are acted on by $S_n$: for $\sigma \in S_n$, define $\sigma(x_i) = x_{\sigma(x_i)}$, etc. Symmetric polynomials are those polynomials which are ...
6
votes
0answers
177 views
+150

An extension of Erdos' distinct distances problem based on circles of various radii

Consider a collection $C_1,C_2, \dots, C_n$ of circles in the plane and suppose that the center of $C_i$ is $o_i$ and the radius of $C_i$ is $r_i$. We will define the relative distance between the ...
3
votes
0answers
65 views

Counting self avoiding walks in a strip

Consider the strip $\{0,1,\ldots n\}\times\{0,1,2\}$ in $\mathbb{N}^2.$ Is a formula known for the total number of self avoiding walks in this strip starting at $(0,0)$ in terms of the parameter $n$? ...
19
votes
1answer
3k views

Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq: Gonthier, Georges. Formal proof—the four-color theorem. Notices Amer. ...
1
vote
1answer
70 views

Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$

Let $\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$ for $r \in \mathbb{N}$. We want to find the the biggest subset of $\Omega$, $\Gamma = \left\lbrace x \in \...
3
votes
1answer
108 views

Reference for Dedekind's problem

Dedekind's problem is about enumerating antichains in the Boolean lattice. Is there an explicit reference where Dedekind stated this problem? Is there a good motivation to study this problem except ...
3
votes
0answers
49 views

Condition for non-existence of trivial matrix decomposition

Let $A_1,\dots,A_n$ be matrices, with no row or column of $0s$, and such that for every $i=1,\dots,n$ there does not exist a decomposition of $A_i$ of the form $$ A_i = \oplus_{j=1}^n B_j \qquad (\...
6
votes
1answer
296 views

Rank and frequency of permutations

(a) Let $[n] = \{1,\dotsc,n\}$, and let $\pi:[n]\to [n]$ be a permutation. Define an $n$-by-$n$ matrix $A=A(\pi)$ as follows: $A_{i,j}=1$ if $j>i$ and $\pi(j)>\pi(i)$, $A_{i,j}=-1$ If $j<i$ ...
8
votes
3answers
509 views

Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
1
vote
1answer
79 views

Circular (bracelets) permutations with alike things(reflections are equivalent) using polya enumeration

Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+..... = N? A similar question exists but it doesn't address the case ...
1
vote
1answer
3k views

Number of graphs with $n$ edges

I have been trying to count the number of graphs up to isomorphism which are: Simple Connected Have $n$ edges. I apologize in advance if there is ample documentation on this question; however, I ...
5
votes
2answers
1k views

A sum involving irreducible characters of the symmetric group

Recently, during the research, I came across a sum, denoted by $H(n,L)$, involving irreducible characters of the symmetric group, \begin{equation} H(n,L)\colon=\sum_{Y_{i,j,w}} \frac{\chi^{Y_{i,j,w}([...
1
vote
2answers
191 views

Constructing a vector consisting of nonnegative entries

Consider constructing a vector $v=(a_1,a_2,\ldots,a_n)$ consisting of nonnegative integers such that $a_1=1$ and, if $a_j$'s are nonzero, then $a_j\equiv a_{n-j+2}+j-1 \pmod m\ \forall 1<j\le\frac{...
2
votes
0answers
114 views

Sum of products of irreducible characters of the symmetric group over a subgroup

When trying to build a dual formulation for lattice gauge theories using Weingarten integration I am getting sums of the kind $$I^{m, n}_{\mu, \nu} (\sigma, \tau) = \sum_{\pi \in S_n} \chi_\mu (\pi \...
30
votes
5answers
5k views

How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each be ...
0
votes
0answers
21 views

hypergraph product that preserve expansion properties

I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2. The expansion property I am looking at is HD-random walk. The product I am looking for is ...
1
vote
0answers
80 views

Relation between the number of spanning trees and the chromatic number of a graph

The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence: $$\tau(G)=\tau(G-e)+\tau(G.e),$$ where $e$ is an edge of the graph $G$ and $G-e$ ...
11
votes
2answers
250 views

Big mono-chromatic subgraphs of vertex 2-colourings

I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V \...
1
vote
1answer
35 views

Vertex connectivity of join of two graphs

Does there exist any results on the vertex connectivity of join of two graphs? If $G_1$ and $G_2$ are two graphs what can we say about the vertex connectivity of $G_1\lor G_2$ where $G_1\lor G_2$ is ...
4
votes
0answers
86 views

program to compute hurwitz numbers

Is there a computer program available to compute Hurwitz numbers easily? In fact I only care about counting covers $C\to\mathbb{P}^1$ branched over $0,1,\infty$, and am even willing to restrict to the ...
1
vote
0answers
130 views

Questions about a certain sequence of naturals generated by primorials

I'm working on the following sequence of naturals (which is NOT listed in OEIS) $$3,5,11,17,23,29,59,89,119,149,179,209,419,629,839,1049,1259,1469,1679,...$$ whose elements are generated this way $$3=(...
2
votes
0answers
60 views

On the proportion of simplicial $d$-polytopes on $n$-vertices

I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices. Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...
1
vote
1answer
53 views

Finding a cycle of a specific length in an edge-weighted graph

I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph. For example, imagine my phone tells me that I need to walk three miles today. It ...
113
votes
61answers
24k views

Important formulas in combinatorics

Motivation: The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...
6
votes
2answers
239 views

Multivariate Lagrange inversion with zero powers

(Also asked on MSE) The multivariate Lagrange inversion formula, which I found in a couple of papers (such as this and this), is as follows. If $f_i=t_ig_i(f)$, $1\le i\le k$, then $$ [t^n]h(f(t))=\...
1
vote
0answers
30 views

Lower bound for the chromatic number in terms of minimum feedback vertex set

Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$. We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$ and this bound is sharp. Is this known or trivial result? This ...
1
vote
0answers
42 views

Yet another graph characteristic

I wonder if the following graph-theoretical concepts have been considered before, and if so, under which name. Consider a directed graph $G$ with $n$ nodes. Let the cycle number $\gamma(\nu)$ be ...
5
votes
1answer
94 views

Parity of shuffle permutations

A $(p,q)$-shuffle is a permutation $\sigma$ of the set $\{1, \dots, p, p+1, \dots,p+q\}$ such that $$\sigma(1)<\dots<\sigma(p)$$ and $$\sigma(p+1) < \dots<\sigma(p+q)\,.$$ It is known ...
3
votes
0answers
130 views

A fusion ring identity

Fusion rings I'll more or less stick to the presentation given in this question: [1] We define a fusion ring as follows: consider a free $\mathbb{Z}$-module $\mathbb{Z}\mathcal{B}$ with finite basis ...
4
votes
1answer
288 views

Is there an integral fusion ring which is not of Frobenius type?

Combinatorially, a fusion ring $\mathcal{F}$ is nothing but a finite set $B=\{b_1, \dots, b_r\}$ (generating the $\mathbb{Z}$-module $\mathbb{Z} B$) together with fusion rules: $$ b_i \cdot b_j = \...
12
votes
1answer
313 views

Yet another real-rooted polynomial

In this entry I asked for the real-rootedness of a polynomial, and two very interesting answers were given: one using Malo's theorem and the other a clever rewriting of the expression using Jacobi ...
0
votes
1answer
85 views

Question of expected number of consecutive coin flip with increasing bias [closed]

This is a question I found on the book and I don't know how to tackle it. Thanks to any help or hint in advance. I have a coin that, I could get the head 100% at the first flip, $\frac{1}{3}$ at the ...
0
votes
0answers
25 views

pseudo-Hadamard matrix

What can one say about the matrices M with the following properties: 1) the rows and the columns are indexed by the elements of a finite field with an even number q of elements; 2) All the matrix ...
8
votes
2answers
323 views

Are these two combinatorially-defined sets of integers disjoint?

Fix an integer $n\geq 8$. For each integer $i\leq n/2$, denote by $X_i$ the set $$X_i = \left\{ \frac{n-i+1-k}{n-i+1}\binom nk\binom{k-1}{i-1} ~\middle|~~ i\leq k\leq n-i\right\}.$$ The ...
0
votes
1answer
53 views

Matching book embedding of Cartesian products of graphs

In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
0
votes
0answers
41 views

A ballot-casting problem

For any set $X$ and cardinal $\kappa$ let $[X]^\kappa$ denote the collection of subsets of $X$ with cardinality $\kappa$. If $n$ is a positive integer, let $[n]:=\{1,\ldots,n\}$. Let $V$ and $K$ be ...
4
votes
1answer
176 views

Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...
8
votes
3answers
418 views

Looking for a “cute” justification for a Catalan-type generating function

The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ have the generating function $$c(x)=\frac{1-\sqrt{1-4x}}{2x}.$$ Let $a\in\mathbb{R}^+$. It seems that the following holds true $$\frac{c(x)^a}{\sqrt{1-...
0
votes
0answers
110 views

Reference for discrete Laplacian on $\mathbb{Z}$

For $x\in \mathbb{R}^\mathbb{Z}$, let the discrete Laplacian be defined as \begin{align*} (\Delta x)_k = 2x_k-x_{k+1}-x_{k-1}. \end{align*} I am looking for good references about its spectrum (or ...
2
votes
0answers
91 views

Solving general two-dimensional recurrence relation

Any techniques for deriving a closed form solution for the following recurrence relation? Or bounds on asymptotic behavior for large $n$? $$a_{n+1,k} = \sum_{0 \le i \le n} \frac{n!}{i!} a_{i,k-1}$$ ...
5
votes
1answer
211 views

RSK correspondence

Up to now, what are the difference ways we know to define RSK correspondence? I already know: By insertion and recording tableau. Ball construction or Viennot's geometric construction. Growth diagram ...

1 2 3 4 5 145