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