# 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.

**0**

votes

**0**answers

29 views

### Are total graph of power of cycles homeomorphic to powers of cycles?

gIs the total graph associated to powers of cycles homeomorphic to powers of cycles themselves? I think yes, because the total graph associated to cycles is homeomorphic to cycles(i think?)So, does ...

**0**

votes

**0**answers

53 views

### Regular intersecting family

Let $n=2k+1$. When $k=3$, the set of lines of Fano plane is a regular intersecting family consisting of some k-subsets of [n]. Do anyone know such examples for general $k$? Thanks.

**1**

vote

**0**answers

55 views

### Has this result about the number of permutations of a given cycle type (or centralizers) been proved?

I was playing with the cardinality of conjugacy classes of the symmetric groups, which we know is the number of permutations of a given cycle type and there is a natural one-to-one correspondence ...

**0**

votes

**0**answers

55 views

### why $e_2\leq (y-1)[\frac{n}{2}-y+1+i]$

Help with this proof:
DEF: Let G be a $(3,l)$-graph. We let $v_i=l−1−i$, and we define $s_i$ to be the number of vertices of G of degree $v_i$.
Let $G$ be a graph and $p$ a point of $G$. By $H_1$ we ...

**0**

votes

**0**answers

57 views

### How many lattices require exactly 3 elements to generate them?

This question by Moshe Newman:
How many different lattices are there on n points, that require
exactly 3 elements to generate them? This sequence seems to start
0,0,1,0,4,3 (for n = 1 to 6) and seems ...

**0**

votes

**0**answers

162 views

### Parity of number of partitions of $n!/6$ and $n!/2$

The parities of the number of partitions of $n!/6$ and $n!/2$ appear to be non-random initially, as follows — is there an explanation for this other than chance? With $p$ being the partition ...

**1**

vote

**0**answers

66 views

### Number of misplaced elements for a partition of a set of coloured items

We are given a set $V$ of $n$ items, where each item is tinted with exactly one color in $C=\{c_1, c_2, \ldots, c_k\}$, in such a way that for each $i\in [k]$ there exists at least one item tinted ...

**4**

votes

**0**answers

103 views

### Absolute oscillator in Langton's Ant

We have a simple (or single) block of Langton's Ants colony which includes two ants looking in the same direction. Their positions can be interpreted as knight's walk. The distances between each next ...

**0**

votes

**1**answer

58 views

### Finding the minimum sum of a subset of entries of a given matrix with combinatorial constraints

Given a matrix $M\in\mathbb{N}^{n\times n}$, let $Z$ be the set of all the $M$'s entry subsets $S$ such that (i) no two entries of $S$ are on the same row or column of $M$ and (ii) $|S|=n$. Clearly we ...

**1**

vote

**0**answers

47 views

### What is known about the combinatorics of the hyperplane arrangement spanned by cyclic polytopes?

Let $1\leq d$ be an integer.
Consider the $d$-dimensional moment curve $\mu\colon \mathbb R\to \mathbb R^d$ given by $t\mapsto (t,t^2,\dots, t^d)$. Given a finite subset $S\subset \mathbb R$ of ...

**0**

votes

**2**answers

53 views

### number of sets including the most popular elements in intersecting sets family

Let $F$ be a set consisting of some subsets of $[n]$, and any two sets in $F$ have at least one element in common. I think I read a result stating as following: there exists an element $x$, such that ...

**0**

votes

**1**answer

36 views

### For an one-order Linear Recurrence of a vector sequence, does the corresponding item follow a Linear Recurrence? [closed]

Consider an one-order Linear Recurrence of a vector sequence, such as
$${\bf x}_{n+1}={\bf A}{\bf x}_n$$
where ${\bf x}_n \in \mathbb{R}^m (\forall n)$, and ${\bf A} \in \mathbb{R}^{m\times m}$ and ${\...

**-2**

votes

**0**answers

45 views

### Subgroup of the internal semidirect product [closed]

Let $H$ and $K$ be a finite groups and $G'$ be a normal subgroup of
the internal semidirect product $H.\,K$. Take $\,H'=\,H \cap \,G'$
and $K'= (G' \,H) \cap \,K$. We can see easely that $\mid G' \mid
...

**10**

votes

**2**answers

680 views

### Determinantal symmetry: proof requested

Consider the determinantal function
$$F(a,b,c):=\det\left[\binom{i+j+a+b}{i+a}\right]_{i,j=0}^{c-1}.$$
I would like to ask:
QUESTION. Can you provide an argument, combinatorial or otherwise, to ...

**1**

vote

**0**answers

65 views

### An alternative proof of a subgroup lattice characterization of the infinite cyclic group

In Schmidt's book Subgroup lattices of groups, Theorem 1.2.5 states that a group $G$ is cyclic if and only if its subgroup lattice $L(G)$ is distributive and satisfies the maximal condition. Its proof ...

**12**

votes

**1**answer

2k views

### Number of positions of Rubik's cube grows with multiplier 13 with the distance - what are explanations and groups with similar growth pattern?

Rubik's cube and its generalizations attracts certain attention of mathematical community. It is somehow "noteworthy" that it has been proved that diameter of the Rubik's cube group is 20, i.e. ...

**1**

vote

**0**answers

27 views

### What is the Advantage of 1-trees over Vertex Splitting?

It is a wellknown fact that the problem of finding an optimal Hamilton tour is equivalent to finding an optimal Hamilton path after a small modification of the problem instance, namely splitting one ...

**5**

votes

**1**answer

93 views

### Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?

Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...

**6**

votes

**0**answers

86 views

### On a certain $(-1)$-Eulerian polynomials of type $B$

Let $(q)_n=(1-q)(1-q^2)\cdots(1-q^n)$ with $(q)_0:=1$. Define a $q$-exponential by
$$e_q(z)=\sum_{n\geq0}\frac{z^n}{(q)_n}.$$
There is a notion of $q$-Eulerian polynomials of type $A$, see the ...

**1**

vote

**0**answers

26 views

### Name for a Lower Bound on the Length of General TSPs and ATSPs

Let $G\left(\ V,\ E=V\times V\setminus\lbrace(v_i,v_i)\rbrace,\ \Omega: E\ni e_{ij}\mapsto\omega_{ij}\in\mathbb{R}\right)$ be a(n) (A)TSP instance.
Then
$$2*\ell(T_{\mathrm{opt}})\quad\ge\quad\sum_{...

**11**

votes

**1**answer

274 views

### Positivity of the coefficients of the Ehrhart polynomial of a cross-polytope

Question 35996 asks about the Ehrhart polynomial $i_d(n)$ of the
standard regular cross-polytope. It can be defined equivalently by
$$ \sum_{n\geq 0}i_d(n)x^n = \frac{(1+x)^d}{(1-x)^{d+1}}. $$
It ...

**1**

vote

**0**answers

56 views

### Treewidth problem equivalence

Say we are solving a tree decomposition problem, e.g.
given a graph $G = (V, E)$ we try to find a chordal graph $H$ such that $V(H) = V(G)$, $E(G) \in E(H)$ and the maximal clique in $H$ is minimal ...

**2**

votes

**1**answer

149 views

### Number of odd elements in a vanishing sum of binomial coefficients

Let $n$ be a positive integer, $k$ a non-negative integer and $N(n,k)$ be the number of odd elements among the numbers $\binom{n+k}{j}\binom{-n-k}{n-j}$, $0\le{j}\le{n}$, which sum to $0.$ It seems ...

**5**

votes

**1**answer

145 views

### A proper definition of connectivity for hypergraphs

For usual graphs on $n$ vertices, a edge-minimal connected graph is nothing but a spanning tree of this graph. It is well-known that any spanning tree has $n-1$ edges.
I would like to know whether ...

**1**

vote

**0**answers

44 views

### Shuffling unordered partitions

Consider the following:
Let $\mathcal{A}$ be an unordered partition of $\{1,\dotsc,p\}$,
Let $\mathcal{B}$ be an unordered partition of $\{1,\dotsc,q\}$
Let $\mathcal{C}$ be an unordered partition of ...

**28**

votes

**10**answers

2k views

### Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...

**3**

votes

**1**answer

97 views

### The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles

Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles.
Clearly, $c(n, 1) = 1$ and it not very hard to ...

**1**

vote

**4**answers

144 views

### Upper and lower bounds on the number of certain subsets of the power set

Let $A$ be a set with $n$ elements. Call a subset $C$ of the power set of $A$ "good" if
Each element of $C$ has at least three elements.
If $P, Q\in C$ and $P\cap Q$ has more than one element, then $...

**2**

votes

**0**answers

66 views

### Inverse theorems for Gowers norms for unbounded functions

The inverse theorem for Gowers norm over finite fields says that if a bounded function $f: V \to C$ where $V$ is a vector space over the finite field $\mathbb{F}$, has large Gowers uniformity norm $\|...

**0**

votes

**0**answers

40 views

### The complexity on calculation of the Graev metric on the free Boolean group of a metric space

For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be ...

**8**

votes

**0**answers

161 views

### q-analog of $(d/dx) \binom{x}{k}$?

It is not hard to find easy formulas for the derivative of the function $\binom{x}{k}$, for instance it is not too hard to see (for $k$ an integer) that
$\frac{d}{dx} \binom{x}{k} = \sum_{i=1}^k \...

**1**

vote

**1**answer

69 views

### Extension of chromatic polynomial to multi graphs

Let $G$ be a multigraph, i.e, there can be more than one edge between a pair of vertices. It is clear that the chromatic polynomial cannot capture these multi-edges. Because chromatic polynomial just ...

**2**

votes

**0**answers

42 views

### Lower and upper (combinatorial) discrepancy

(I will state my question in terms of combinatorial discrepancy, but the same could be also asked about measure-theoretic discrepancy as well.)
The combinatorial discrepancy of a family $\mathcal F$ ...

**0**

votes

**1**answer

61 views

### Coloring a complete regular hypergraph

For any set $X$ and positive integer $k$ denote by $[X]^k$ the set of subsets $S\subseteq X$ such that $|S|=k$.
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $...

**2**

votes

**1**answer

50 views

### Lower bound on the number of solutions of N-queens problem

The OEIS lists the number of solutions of N-queens problem
(Number of ways of placing n nonattacking queens on an n X n board). However, no formula is given. It is easy to observe that each number in ...

**0**

votes

**0**answers

245 views

### A question on the Faulhaber's formula

Proposition 1.1
For every integers $m,n\geq 0$ the following identity holds
\begin{equation}
n^{2m+1}=\sum_{k=1}^{n}\sum_{j=0}^m A_{m,j}k\strut^j(n-k)\strut^j=\sum_{k=0}^{m}(-1)^{m-k}U_m(n, k)\cdot n\...

**4**

votes

**2**answers

240 views

### “Locally Nonplanar” graph

A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and ...

**1**

vote

**2**answers

120 views

### Is a vertex- and edge-transitive polytope already a uniform polytope?

I want to consider (convex) polytopes $P=\mathrm{conv}\{p_1,...,p_n\}\subset\Bbb R^d$ which are both, vertex- and edge-transitive (or maybe stronger: 1-flag-transitive).
Question: Is every such ...

**4**

votes

**0**answers

137 views

### Distribution of point knowing target in optimal matching

I am a young PhD student in statistics.
Recently, papers (Ambrosio, Stra and Trevisan; Talagrand; Ledoux to cite but a few) tackled the problem of finding the expected cost in an optimal matching, ...

**1**

vote

**1**answer

76 views

### Evaluation of a complete homogeneous symmetric polynomial related to Stirling number of 2nd kind

It is well known that the complete homogeneous symmetric polynomial $h_{n-k}(1,\,2,\,3, ...,\,k-1,\,k)$ equals $S(n,\,k)$ the Stirling number of the second kind. [Wikipedia]
During a research project ...

**2**

votes

**0**answers

106 views

### Concerning the identity in sums of Binomial coefficients [closed]

Consider the following identity
$$\sum_{k=1}^{n}\binom{k}{2}=\sum_{k=0}^{n-1}\binom{k+1}{2}=\sum_{k=1}^{n}k(n-k)=\sum_{k=0}^{n-1}k(n-k)=\frac16(n+1)(n-1)n$$
As we can see the partial sums of binomial ...

**4**

votes

**0**answers

69 views

### Minimum number of balanced partitions

For any multiset $x_1,x_2,\ldots,x_{2n}$ of positive real numbers, a partition into two nonempty subsets $(A,B)$ is called "balanced" if $\text{sum}(A)\geq\text{sum}(B)-\max(B)$ and $\text{sum}(B)\geq\...

**0**

votes

**1**answer

99 views

### A question on “SUM-PRODUCT…VIA KLOOSTERMANN SUMS”, by Hart, Iosevich and Solymosi

In this paper https://arxiv.org/pdf/math/0609426.pdf, the authors, state, as a consequence of Theorem 1.1, the following sum-product estimate.
Theorem 1.1 says that for all $A\subset\mathbb{F}_q$, we ...

**1**

vote

**1**answer

79 views

### Graphs formed of vertices of distance $2$

Let $G=(V,E)$ be a finite, simple, undirected graph. Let $D_2(G)$ be the graph with vertex set $V$, and two vertices form an edge if and only if they have distance $2$ in the original graph $G$.
...

**-2**

votes

**0**answers

66 views

### Possible inclusion-exclusion (?) for number of triangles [migrated]

I am looking for some reasoning in Chatterjee's paper here (page 3) (also picture below) of the bound on the number of triangles in the random graph $G(n,p)$ of n verticies and each edge is present ...

**2**

votes

**0**answers

19 views

### Graph vertex label dynamics, statistical model reference request

I am modeling some type of social interaction, and came up with the following natural question.
Let $K_n$ be the complete graph on $n$ vertices, with some initial edge labeling in some alphabet $A$.
...

**0**

votes

**1**answer

76 views

### Size of edge set of infinite hypergraphs with $\chi(H) = |V(G)|$

Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...

**0**

votes

**0**answers

47 views

### Confirming existence in polynomial time while solution finding is NP-complete

Assume P≠NP.
Say there's an NP-complete decision problem:
Does $P$ have a $Q$ ?
And we have a proposition $F$ computable in polynomial time, where $F(P)$ implies the existence of a solution in ...

**2**

votes

**0**answers

66 views

### Does the period of the first row in the odd size bad Laver tables grow without bound?

Does the length of the period of the first row in the odd bad laver tables grow without bound?
If $n$ is a natural number, then the $n$-th bad Laver table is the algebra $B_{n}=(\{1,...,n\},*)$ where
...

**3**

votes

**1**answer

148 views

### Graph isomorphism by invariants

Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.
Let us call a (numerical) ...