Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
10answers
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
1answer
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
4answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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) ...