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

How many possible combinations [closed]

How many possible combinations ? Hi, I have provided a picture to explain. Each Lettered card can be true or false. So an Example if A,C,F are enabled there will be less combinations than if A,B,C,E ...
user avatar
-2 votes
0 answers
37 views

Sum-product estimate: Let A ⊂ Z/qZ be any set not containing zero with |A| > √ 2q 5/8 . Show that (A + A) · (A + A) + A · A + A · A = Z/qZ [closed]

https://gshakan.files.wordpress.com/2016/04/discretefouriertransform1.pdf Is there any idea to prove exercise 1.11? I tried to use above techniques but it seems quite hard.
user avatar
  • 1
3 votes
1 answer
123 views

Has the following problem, resembling the lonely runner conjecture, been studied?

Given $n$, what is the smallest value $\delta_n$ satisfying the following: For any group of $n$ runners with constant but distinct speeds, starting from the same point and running clockwise along the ...
user avatar
5 votes
0 answers
86 views

Determinant of matrix with Stirling numbers as elements

After noticing that the determinant of an $n \times n$ matrix $A_n$ with elements $a_{i,j}=i^j$, $1 \le i \le n$, $1 \le j \le n$, is the superfactorial (product of the first $n$ factorials), I wanted ...
user avatar
  • 326
2 votes
0 answers
49 views

Odious twin locations related to the sequence based on $d(n) = n-d(d(n-1))-d(d(n-2))$

Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Let $a(n)$ be the sequence of numbers $k$ such that $\operatorname{wt}(k)\...
user avatar
6 votes
0 answers
77 views

Alon-Füredi for special polynomials

A theorem of Alon and Füredi says that if $A$ and $B$ are finite, nonempty subsets of the field $\mathbb F$, and if a polynomial $P(x,y)\in\mathbb F[x,y]$ vanishes on all, but exactly one point of the ...
user avatar
  • 21.3k
15 votes
2 answers
535 views

Indecomposable contracting maps on the integers

$\def\ZZ{\mathbb{Z}}$Call a function $f : \ZZ \to \ZZ$ "contracting" if $$|f(j) - f(i)| \leq |j-i|$$ for all $i$, $j \in \ZZ$. The contracting functions form a monoid under composition; call ...
user avatar
2 votes
1 answer
110 views

Can connectivity be less than min cut/degree?

Suppose we have a graph with min-cut $\lambda$ and minimum degree $> \lambda$. Is it possible for there to be a vertex that is at most $\lambda$-connected to every other vertex in the graph? ...
user avatar
  • 23
3 votes
3 answers
92 views

An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ordered tuple of all balanced $l$-bit binary sequences

Assuming that $l>1$ is even, an $l$-bit binary sequence $b$ is balanced if and only if the number of zeroes in $b$ is equal to $l/2$. Let $T_l$ denote a lexicographically ordered tuple of all ...
user avatar
4 votes
0 answers
127 views

Why are these Littlewood-Richardson coefficients congruent to 1 mod 8?

Let $n\in{\mathbb N}$ and write $n=q_1+q_2+\dots+q_t$, where $q_1>q_2>\dots>q_t$ are powers of $2$. Let $\lambda_n$ be the partition with Frobenius symbol $(q_1-1,q_2-1,\dots,q_t-1;q_t,q_{t-1}...
user avatar
3 votes
0 answers
128 views

Binary iterations, Fibonacci numbers and permutation of natural numbers

Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Also let's consider $$\ell(n)=\left\lfloor\log_{2} n\right\rfloor$$ and $$T(n,...
user avatar
2 votes
1 answer
50 views

fills a given polygon with a few types of given primitives

Given one large 2D polygon, and K types of small polygons (the primitives). For each type of small polygon, it can be rotated, and has an infinite number of pieces. For such a Jigsaw puzzle game, is ...
user avatar
-1 votes
0 answers
34 views

How many combinations of strings of length m consisting of n digit types are there? [closed]

I'm looking to find a formula for the number of combinations there are given a string of a fixed length and a certain number of available digits. Example: A string of length 6 containing 3 Xs and 3 Os ...
user avatar
0 votes
0 answers
52 views

Cutsets and disjoint edge sets in graphs

If $H=(V,E)$ is a hypergraph then we say that $C\subseteq V$ is a cutset if $C\cap e \neq \emptyset$ for all $e\in E$. We set $$\text{cut}(H) = \min\{|C|: C \text{ is a cutset of }H\}.$$ A subset $D\...
user avatar
1 vote
1 answer
147 views

"Lamp-switch set-up number" of $n$ [closed]

Motivation. The following has a real-life (!) inspiration from a discussion about how to connect lamps and switches in an efficient way. Question. Let $n\in\mathbb{N}$ be a positive integer and let $\{...
user avatar
4 votes
1 answer
117 views

Strongly minimal covers for clique hypergraphs of graphs

$\DeclareMathOperator\Cliq{Cliq}$A hypergraph $H$ is a pair consisting of a set $V$ of vertices and a family of subsets of $V$ called edges. One class of examples is obtained by taking a graph $G=(V,E)...
user avatar
  • 1,064
2 votes
0 answers
88 views

A closure property of a set partition

Let $A$ be a finite set, $k\in\mathbb N$, $\tilde A\subset A^k$ and $\phi: \tilde A\to A$ be a map. Consider the following property a set partition $P$ of $A$ might have: $$ \forall B_1,\dotsc,B_k\in ...
user avatar
  • 5,009
7 votes
1 answer
208 views

A curious $q$-series identity on a truncated Euler function

Recall that a $q$-Pochhammer symbol is defined as $$ (x)_n = (x;q)_n := \prod_{l=0}^{n-1}(1-q^l x). $$ I found the following curious $q$-series identity that seems to hold for any $n\geq 0$: $$ (-1)^{...
user avatar
  • 1,400
4 votes
1 answer
112 views

Find all 2-planar drawings of $K_6$ and $K_7$

A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per edge. It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$. Angelini P., Bekos M. A., ...
user avatar
1 vote
0 answers
95 views

On probability of coprimality of a list of numbers

We know $r$ randomly chosen integers are coprime with probability $\frac1{\zeta(r)}$. Pick a bound $N$ and pick $k\lceil N^{\alpha}\rceil$ uniformly random integers in $[0,N^{\alpha+\beta}]$ where $\...
user avatar
  • 12.9k
4 votes
1 answer
220 views

Explicit expression for recursive sums - II

A twist on just unfolded recursive summation formula. Let polynomials in nonnegative integer variables $t_1,t_2,\dots$ be defined by the recurrence: \begin{split} g_0 &= 1, \\ g_k(t_1,t_2,\dots,...
user avatar
2 votes
1 answer
64 views

Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two

Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is ...
user avatar
  • 343
0 votes
0 answers
72 views

Has the mixture of forward and backward finite difference existed?

Given a function $ f(x) $, there are forward and backward finite differencs, whose definitions are given in the following. By forward one, we mean $ \Delta f(x) = f(x+d)- f(x) $, $(d>0)$; and by ...
user avatar
9 votes
0 answers
204 views

Hives for other root systems? [duplicate]

Littlewood-Richardson coefficients $c^\lambda_{\mu\nu}$ have numerous combinatorial interpretations, including the hive model by Knutson and Tao, see here. For other root systems, there are also ...
user avatar
  • 15.2k
4 votes
0 answers
85 views

Almost acyclicity of the complex of configuration spaces of noncollinear points in projective plane over finite fields

Let $F$ be a finite field with many elements, say more than 7 for example, and $X$ be the corresponding projective plane $\mathbb{P}^2(F)$. For a set of points in $X$, if any three of them are ...
user avatar
2 votes
1 answer
263 views

Prove positivity of rational functions

We say a rational function $F(z)$ is positive if the coefficients of its Maclaurin expansion, in the variable $z$, are non-negative. In this context, let $$F_r(z):=\frac{1 - 2z + z^r - (1 - z)^r}{(1 - ...
user avatar
10 votes
2 answers
412 views

Explicit expression for recursive sums

Let $t_1,t_2,\dots,t_k$ be non-negative integers. Can the following sum $$f_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+j_1} \sum_{j_3=0}^{t_2+j_2} \dots \sum_{j_k=0}^{t_k+j_{k-1}} 1$$ ...
user avatar
7 votes
2 answers
192 views

On permanent of a square of a doubly stochastic matrix

Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is ...
user avatar
0 votes
0 answers
74 views

Efficiency of covers

Let $X\neq \emptyset$ be a set. We say $C \subseteq {\cal P}(X)$ is a cover of $X$ if $\bigcup C = X$. For covers $C, D$ of $X$ we say that $C$ is more efficient than $D$ if $|C\setminus D| < |D \...
user avatar
4 votes
2 answers
94 views

$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products

Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game: Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. ...
user avatar
  • 41
0 votes
0 answers
64 views

Optimal covering trails in 3 and 4 dimensions

A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...
user avatar
  • 1
0 votes
0 answers
72 views

Inverse limit in category of graphs

Let $... \leftarrow G_i \leftarrow G_{i+1} \leftarrow ...$ be an inverse system of graphs (which might not be locally finite), morphisms are symplicial maps (we allow collapsing of edges to vertices)....
user avatar
2 votes
0 answers
77 views

A minimal size of a set of tuples for an upper bound of a distance between any pair of elements

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
user avatar
5 votes
1 answer
526 views

Much weaker condition for Kakeya sets over finite fields

What is the minimum size of a subset $S \subseteq \mathbb{F}_p^n$ such that for all directions $a \in \mathbb{F}_p^n$, there is a line in direction $a$ that intersects $S$ in at least $C$ points? If $...
user avatar
  • 101
6 votes
0 answers
113 views

Number of tautologies of a given size?

Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...
user avatar
  • 383
1 vote
0 answers
84 views

Are there standard short notations for ascending and descending cyclic permutations?

In a paper I am currently writing I use cyclic permutations of the form $$ (k,k+1,\dots,\ell) $$ and $$ (\ell,\ell-1,\dots,k) $$ of consecutive elements quite a lot (I added the commas to avoid ...
user avatar
  • 5,661
15 votes
1 answer
370 views

Make $n$ numbers equal using pairwise averages

Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is ...
user avatar
  • 151
22 votes
1 answer
3k views

Can an odd number of marbles jump to infinity?

Loosely inspired by the game Abalone, I've encountered the following simple problem I cannot solve. Suppose that we are given a finite set of marbles on an infinite chessboard. One move consists of ...
user avatar
  • 17.1k
2 votes
0 answers
77 views

Reference request on Plancherel measure for partitions whose parts differing by more than $1$

Given an (unrestricted) integer partition $\lambda$ of $n$, let $f_{\lambda}$ denote the number of standard Young tableaux (SYT) of shape the Young diagram $Y(\lambda)$ of $\lambda$. Then, $$\sum_{\...
user avatar
4 votes
1 answer
177 views

A combinatorial question about certain sequences

Consider the sequence defined by the following algorithm: Make a stack of tickets numbered from 1 to $n,n>1 \in N$ and arranged in reverse order with the ticket numbered 1 at the bottom and that ...
user avatar
0 votes
0 answers
61 views

Expectation of edge weights on the complete graph, Part 2

This question concerns the same basic set-up as my previous question: Expectation of edge weights on the complete graph In that question an answer was given which shows that the expected value is as ...
user avatar
3 votes
1 answer
143 views

Total number of plane partitions for $4$ or more dimensions

According to MacMahon formula the total number $P_3(r, s, t)$ of plane partitions that fit in the $r \times s \times t$ box $\mathcal{B}(r,s,t)$ is equal to the following product formula: $$ P_3(r,s,t)...
user avatar
  • 326
1 vote
1 answer
132 views

Expectation of edge weights on the complete graph

Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
user avatar
7 votes
1 answer
221 views

Harmonic flow on the Young lattice

Let me begin with some preliminary concepts: A positive real-valued function $\varphi: P \rightarrow \Bbb{R}_{>0}$ on a locally finite, ranked poset $(P, \trianglelefteq)$ is harmonic if $\varphi(\...
user avatar
3 votes
1 answer
137 views

Existence of wild regular abstract polytopes

Is it possible for an edge to connect two non-adjacent vertices of a polygonal face in a regular abstract polytope? Here “adjacent” means that the two vertices are connected by an edge that is a facet ...
user avatar
0 votes
0 answers
53 views

Determining the total number of nonzero expansion terms in a (0,1)-matrix

Let $A=(a_{ij})_{n\times n}$ be a $(0,1)$-matrix such that it contains equal number of $1$s in each row and column. Is there any general method to count the total number of the nonzero terms $\prod_{i=...
user avatar
  • 133
1 vote
0 answers
87 views

$r(M)$-subsets of a 3-connected matroid $M$

It is proved in Lowrance, Oxley, Semple, and Welsh - On properties of almost all matroids that almost all matroids are 3-connected asymptotically. Also, it is conjectured that almost all matroids are ...
user avatar
  • 359
4 votes
1 answer
232 views

Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting. ...
user avatar
  • 43
2 votes
0 answers
47 views

Does periodic pattern arise in syndetic pattern

We wonder for two "large" sets $I,J\subseteq \omega$, if $(J-J)\cap I=\emptyset$, then it must be due to certain periodic pattern. We say $I\subseteq \omega$ is $t$-syndetic iff for every $n\...
user avatar
  • 909
0 votes
0 answers
56 views

Shattering of a set of binary classifiers

Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$. Here is what ...
user avatar
  • 101

1
2 3 4 5
185