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.
-4
votes
1answer
41 views
Regular graph such that $2$ distinct vertices have same neighborhood set
If $G=(V,E)$ is a simple, undirected graph and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$.
Is there an integer $k>1$ and a connected $k$-regular graph $G=(V,E)$ such that there are $v\neq ...
-2
votes
0answers
53 views
Birthday Calendar Gaps [on hold]
I work at a company that posts a birthday calendar. I noticed that there was a string of four consecutive days with no birthdays. What is the probability of that happening?
Problem Statement
Given n ...
0
votes
0answers
113 views
Total number of collisions
Given $n$ point masses on the real axis with their initial positions and velocities, determine the total number of collisions (from $t=0$ to $t=\infty$). Here I suppose that the collisions are elastic,...
0
votes
0answers
36 views
Average distance between a random point and the closest of a set of random points
Create a set of n randomly placed points in a unit square. Then create another random point in the unit square. What is the average distance between this point and the closest of the n points?
2
votes
2answers
115 views
Infima and suprema in the “transfer” function ordering
Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...
3
votes
0answers
118 views
Combinatorics question
Let $A = (a_{ij})_{1\le i,j\le h}$ be an $h$-by-$h$ non-degenerate upper triangular matrix with entry $a_{11} = 1$. Let $\Phi = \{\alpha_1,\alpha_2,\ldots,\alpha_d\}\subseteq \{1,2,\ldots,h\}=I$ be an ...
0
votes
0answers
74 views
How to prove the exact top degree of the polynomial coming from each Feynman diagram?
Let $W=x_0+x_1+x_2+\lambda_0 \ln(x_0)+\lambda_1\ln(x_1)+\lambda_2\ln(x_2)+(\frac{x_0x_1x_2}{q})^{\frac{1}{3}}$, where $\lambda_i=\xi^i\cdot\lambda$, $\xi$ is the 3-th root of unit. For each Feynman ...
8
votes
0answers
194 views
Commuting matrix variety $[A,B]=0$ - can one geometrically explain divisibility of $F_ q$ point count by high powers of $q$?
$\DeclareMathOperator\Comm{Comm}\DeclareMathOperator\Id{Id}$Consider the variety $\Comm$ of commuting matrices $[A,B]=0$ over some field $K$. It is much studied, and interesting for various reasons.
...
3
votes
0answers
48 views
Biggest Cartesian Product Included in a Real Plane Curve
Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
1
vote
1answer
88 views
Incidences between points and circles in the plane
Suppose we have $n$ points $P$ and $m$ circles $C$ in the plane. Let $I(P,C)=\{(p,c), p \in P, c \in C, p \in c\}.$ Then what do we know about
$\max_{m,n} |I(P,C)|$?
Any references?
4
votes
2answers
109 views
Are cyclic codes bounded by a continuous function?
In coding theory, we know that if you take the function
\begin{equation}
\alpha_q(\delta) := \limsup_{n \rightarrow \infty} \ \max \{ R(C) \mid \delta(C) \ge \delta \mid C \subseteq \mathbb{F}_q^...
-1
votes
1answer
104 views
Version of Hall's marriage theorem in arbitrary finite graphs [closed]
Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge).
For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\...
2
votes
0answers
109 views
Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)
In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
3
votes
0answers
117 views
Maximum number of integral roots in degree $d$ polynomial?
Given $f(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$ such that
Each coefficient is bound in absolute value by $B$
Degree of each variable in any monomial is bound by $d$
Total degree is $d'$
$f(x_1,\...
2
votes
0answers
99 views
On an exercise in The Probabilistic Method : random dilate of a set in a finite field
This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following:
Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...
5
votes
2answers
141 views
Enumeration of lattice paths of a specific type
One of the approaches to "Special" meanders led (in particular) to the following question:
What is the number $a_{m,n}(\ell)$ of $\ell$-step paths from $(1,1)$ to $(m,n)$ using the ...
6
votes
2answers
106 views
Neighboring number of a permutation
For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ ...
18
votes
1answer
481 views
Order of Conway's “look and say” recurrence
Let $L_n$ be the length of the $n$th term of Conway's "look and say"
sequence (https://oeis.org/A005341). The generating function $F(x)=
\sum_{n\geq 0}L_nx^n$ is a rational function, say $P(x)/Q(x)$ ...
2
votes
0answers
118 views
What kind of curve is this, from the distribution of roots of Catalan polynomials? [closed]
We consider the distribution of roots of some Catalan polynomials.
And we get the following curve that the roots approach it.
What kind of curve is this?
5
votes
1answer
208 views
On the “infinitely often in” relation between subsets of $\mathbb{N}$
Let ${\mathbb N}$ denote the set of positive integers, let $A,B\subseteq \mathbb{N}$. For $n\in\mathbb{N}$ we set $n+A:=\{n+a: a\in A\}$. We say that $A$ is infinitely often in $B$ if the set $$\big\{...
3
votes
1answer
109 views
Expected size of the smallest preimage set
Let $f$ a function from $\{0, 1 \}^{2n}$ to $\{0, 1 \}^{n}$ uniformly picked at random. I would like to have an estimation of the expected size of the smallest premiage set of $f$, more formally $\...
2
votes
0answers
51 views
Total Coloring Conjecture for Cayley Graphs
The total Coloring Conjecture(TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
2
votes
0answers
58 views
Algebraic description of the reduced incidence algebra of a poset
In the book "Combinatorial theory" by Martin Aigner (from 1979), the standard algebra of a poset is introduced as the subalgebra of the incidence algebra of a poset consisting of the functions that ...
2
votes
1answer
110 views
Does the likelihood of these tables exist?
Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.
Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...
14
votes
1answer
617 views
Combinatorial inequality for dominant dimension
In the following I present a conjecture on Nakayama algebras that I have for nearly 2 years now. Since I was not able to solve it and it can be stated purely combinatorically, I thought it might be ...
7
votes
0answers
83 views
Permutation groups with diameter $O(n \log n)$
I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
1
vote
0answers
36 views
Examples of associative inducers and other inducers
I am curious about how well the following technique can produce algebraic structures and semigroups in particular.
Let $(X,\circ)$ be a semigroup. Let $Y$ be a set and let $L:X\rightarrow P(Y)$ be a ...
4
votes
1answer
95 views
Hamming representability of finite graphs
This is a follow up on an older question.
We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of ...
0
votes
1answer
102 views
Conjecture on representing graphs within $\{0,1\}^n$
We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of the set $\{ i \in \{0, ..., n-1\} : x(i) \...
2
votes
1answer
99 views
How to uniformly sample a square (0,1)-matrix whose trace is 0 and whose row sums and column sums are the same?
Happy New Year!
Suppose I would like to sample a $n \times n$ (0,1)-matrix whose trace is 0, and whose row sums and column sums are all $m$ with $1 \le m \le n-1.$ How can I sample this matrix ...
11
votes
1answer
276 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:
...
1
vote
0answers
119 views
How often do random games of go end in illegal moves?
Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...
4
votes
2answers
179 views
How many ways to fill in a square grid with certain restrictions
Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 ...
0
votes
4answers
317 views
How to compute this series: $\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$ [closed]
How to compute this series: $$\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$$ where $C_k$ is the catalan number: $C_k=\frac{1}{k+1}{2k \choose k}$. (Further, is there any general method to treat this ...
1
vote
1answer
59 views
Enumerating isomorphic subgraphs
For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...
4
votes
1answer
297 views
Spreading $n$ points in $\{0,1\}^n$ as far as possible
Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$
We say that a positive integer $s$ is $...
5
votes
1answer
191 views
Inequality number of facets simplicial complex
In a recent preprint, Adiprasito proves that if $\Delta$ is a simplicial complex of dimension $d$ that can be embdedded in a $2d$-dimensional homology sphere (say $\Sigma$) that satisfies a version of ...
6
votes
0answers
203 views
Is the permanent of the matrix $[(\frac{i+j}{2n+1})]_{0\le i,j\le n}$ always positive?
Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by
$$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$
In 2004, R. Chapman [Acta ...
0
votes
1answer
71 views
Finding a good transversal basis
A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...
5
votes
2answers
283 views
The number of Dyck paths of length $2n$ and height exactly $k$
In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions.
For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we ...
1
vote
1answer
97 views
On a theorem of Chetwynd and Hilton in Graphs
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
1
vote
0answers
91 views
Has the “semidirect monoid of a semiring” been considered anywhere?
Given a semiring $S$, we get a monoid $M(S)$ as follows:
The underlying set of $S$ is $S^2$
The identity element is $(0,1)$
The law of composition is given by $$(a,A)(b,B) = (Ba+b,AB),$$ where $a,A,b$...
1
vote
0answers
86 views
extending a partition of a number to get new partition
Let $\lambda = (k_1^{m_1}\,k_2^{m_2})$ where $0<k_1<k_2$ be a partition of $n$ in the power notation.
Let $\mu = p_0^{r_0}\,p_1^{r_1}\,\cdots\, p_t^{r_t} \,(k_1^{m_1}\,k_2^{m_2})\,q_0^{s_0}\,...
-2
votes
1answer
216 views
Negative Dirichlet Pigeonhole Principle
From Dirichlet Pigeonhole Principle if $p$ is a prime and if $a,b\in\mathbb Z$ are in $(0,p/2)$ then there is a $t\in(0,p)\cap\mathbb Z$ such that $\|(x,y)\|_\infty<\lceil\sqrt p\rceil$ holds where ...
2
votes
1answer
252 views
Homogeneous van der Waerden
The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$.
...
1
vote
2answers
250 views
Prove that there exists a nonempty subset $ I$ of $ \{1,2,…,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer
Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...
4
votes
1answer
211 views
Applications of De-Bruijn Sequences in “Pure Mathematics”
I know of a few applications of De-Bruijn Sequences and De Bruijn Graphs in combinatorics, applied mathematics, Engineering and computer science. But I have only found one application of De Bruijn ...
8
votes
1answer
153 views
On the existence of a particular type of finite measure on $\mathbb N$
Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...
0
votes
0answers
46 views
Polynomial time way of testing optimality of given vertex for linear programming
Is there a fast way (polynomial complexity) of testing whether a given vertex for a linear program is optimal, without assuming non-degeneracy?
I can find the optimal vertex in worst-case polynomial ...
2
votes
1answer
58 views
Stretching map of $n$ points from $\{0,1\}^n$ to $\{0,1\}^{n+1}$ with respect to their Hamming distance
Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$
Given an integer $n>0$ and a set $S\...
