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

More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...
Wolfgang's user avatar
  • 13.2k
4 votes
2 answers
616 views

How to know if convex-hull of a set contains zero?

Let $(\lambda_1 , \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Is there any way to decide if $0 \in \text{Conv}\{(\underbrace{\alpha_1, \cdots, \alpha_1}_{\lambda_1}, \cdots , \...
SMD's user avatar
  • 480
4 votes
0 answers
141 views

Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$

We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
Penelope Benenati's user avatar
4 votes
2 answers
488 views

Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?

Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...
Thomas Edison's user avatar
4 votes
2 answers
231 views

Distribution of $0$-$1$ matrices

Consider $n\times n$ matrices with entries in $\{0,1\}$. The determinants of these ranges from $0$ to the Hadamard bound $\frac{(n+1)^{\frac{n+1}2}}{2^n}$. Assume $n$ is large enough. What does the ...
Lewi_Sol's user avatar
  • 309
4 votes
1 answer
678 views

Seymour's second neighborhood conjecture

Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.
hbm's user avatar
  • 1,034
4 votes
3 answers
327 views

Diagonal asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
Mladen's user avatar
  • 43
4 votes
1 answer
814 views

Existence of triangle-free graphs for regular graphs of degree at most n/2

It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to half the number of vertices (...
Gizem's user avatar
  • 43
4 votes
0 answers
221 views

Efficiently computing (plethysm-like?)substitutions of symmetric functions

This is a rather technical question, it arose in connection of some calculations that I need to have better grasp of the question Formal group law over $\mathbb{F}_p$ and my own older one What is ...
მამუკა ჯიბლაძე's user avatar
4 votes
1 answer
371 views

Existence of a non-Eulerian atomistic lattice with this property on the Möbius function

Let $L$ be a finite lattice with least element $\hat{0}$, greatest element $\hat{1}$, and Möbius function $\mu$. Question 1: What class of lattices the following property characterizes? $$\mu(\hat{0},...
Sebastien Palcoux's user avatar
4 votes
1 answer
255 views

Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?

This question is a follow-up of this question. Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd. Question: Can we compute the exact minimum $$A:= \min_{u:\mathbb{...
Asaf Shachar's user avatar
  • 6,611
4 votes
1 answer
214 views

Enumerating matrices function of ranks

Is there an expression/approximate expression for number of real matrices $M\in\{0,1\}^{n\times n}$ of rank $r\leq n$? Is it known if $M$ is restricted to symmetric/skew-symmetric matrices? Does ...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
626 views

Complete graph coloring with cycle restriction

The following question is probably open (It was posted on AoPS a long time ago, but no one has a solution) We have a complete graph with $n$ vertices. Each edge is colored in one of $c$ colors such ...
mathstudent1902's user avatar
4 votes
0 answers
174 views

Determine binary function $f(x)$ by partial observation of $x$

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f:...
Lwins's user avatar
  • 1,531
4 votes
1 answer
839 views

New edge coloring problem in graph theory

Let $G$ be a simple graph. Consider the following edge coloring: We are allowed to use repetitive colors on some edges incident to a vertex such that the result does not contain a sequence of length $...
C.F.G's user avatar
  • 4,165
4 votes
1 answer
185 views

On a double sum involving binomial coefficients

For natural $n$, let \begin{equation} p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l) \sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1} \end{equation} where $k:=\lfloor(n+1)/...
Iosif Pinelis's user avatar
4 votes
0 answers
95 views

Counting cycles after permuting within rows and columns

Consider a rectangular $p \times q$ array, labelled by the numbers $0, \ldots, pq - 1$ for convenience. Let $S_p$ and $S_q$ and $S_{pq}$ denote the symmetric groups. Take a family of permutations: $...
Marty's user avatar
  • 13.1k
4 votes
1 answer
532 views

genus zero permutation and noncrossing partition

Question Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), ...
anecdote's user avatar
  • 165
4 votes
2 answers
404 views

How big must the sumset $A+A$ be if $A$ satisfies no translation-invariant equations of low height?

Suppose $A$ is a finite subset of an abelian group. If there is no solution to $ma+nb=(m+n)c$ with $0\leq m,n\leq M$, can we bound $|A+A|$ from below? I am interested if one can obtain bounds much ...
deadcat's user avatar
  • 41
4 votes
0 answers
200 views

Extract this constant term

Given a Laurent polynomial $F$ in the variables $\mathbf{t}=(t_1,\dots,t_n)$, let $CT_{\vec{\mathbf{t}}}\,F$ denote its constant term. For example, $CT_{t_1,t_2}((8t_1-\frac1{3t_1t_2})(5t_1t_2+t_2^2+\...
T. Amdeberhan's user avatar
4 votes
1 answer
924 views

What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...
blt's user avatar
  • 1,203
4 votes
1 answer
291 views

Number of walks on integer lattice with self-edge at zero

Consider the graph with vertices $V=\mathbb Z$ and edges $$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$ that is, the usual integer lattice with a self-edge at zero. For some fixed parameters $a,b,n\in\...
Raisin Bread's user avatar
4 votes
1 answer
288 views

Collecting stones in n buckets

There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new ...
Maurizio Monge's user avatar
4 votes
0 answers
195 views

A matroid parity exchange property

As part of my research, I encountered the following problem. Let $M = (E,I)$ be a matroid and let $P = \{P_1,\ldots,P_n\}$ be a partition of $E$ into (disjoint) pairs. For $A \subseteq P$, we say that ...
John's user avatar
  • 161
4 votes
2 answers
656 views

"half arithmetic progressions" in dense sets

Fix a positive real number d>0. Szemeredi's theorem implies that for every integer k, there exists an integer N(k,d) such that if A is a subset of the interval [1,N] with density greater than d >0, ...
Mark Lewko's user avatar
  • 11.7k
4 votes
0 answers
186 views

Polynomials of growth for finite Heisenberg groups

Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes. For example for $H_3(Z/...
Mikhail Evseev's user avatar
4 votes
0 answers
214 views

Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$. For any coloring $c:V(G) \...
Dominic van der Zypen's user avatar
4 votes
0 answers
103 views

Can we extend "every finite lattice is a sublattice of partitions of a finite set" to linear and/or finitary lattices?

Pudlák and Tůma https://link.springer.com/article/10.1007/BF02482893 proved that every finite lattice can be embedded as a sublattice of the partition lattice of a finite set. Can this be generalized ...
Dale's user avatar
  • 431
4 votes
2 answers
2k views

How to compute the rook polynomial of a Ferrers board?

Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...
didest's user avatar
  • 1,015
4 votes
0 answers
104 views

Weighted maximal number of disjoint singly-generated ideals in the divisibility poset for $\{1,2,\ldots,n\}$

In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual ...
kodlu's user avatar
  • 10.1k
4 votes
2 answers
560 views

Combinatorial interpretation for coefficients of reciprocal of power series

I've seen a number of combinatorial interpretations for the coefficients of the compositional inverse (aka reversion) of a power series. Is there a known combinatorial interpretation for the ...
David Galvin's user avatar
  • 1,112
4 votes
0 answers
808 views

Number of arrangements that contain at least 1 path from top to bottom of 2D matrix

I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white. With that information, I can easily calculate the total number of black element arrangements that exist ...
Cardstdani's user avatar
4 votes
0 answers
252 views

What is $\dim D^{\lambda}$ for the symmetric group?

What are the dimensions of the simple modules $D^{\lambda}=S^{\lambda}/S^{\lambda}\cap (S^{\lambda})^{\perp}$ for the modular representation theory of $S_n$, i.e. $\operatorname{char}(k)=p>0$? I ...
Jackson Walters's user avatar
4 votes
1 answer
534 views

Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S=\{013,026,045,124,156,235,346\}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below. \[L=\left(...
Douglas S. Stones's user avatar
4 votes
1 answer
223 views

Asymptotics for 'generalized" Kasteleyn's formula

A follow up on an earlier MO question. Kasteleyn's formula for the number of domino tilings of a $2n\times 2n$ square $\prod_{j=1}^n\prod_{k=1}^n \left( 4\cos^2(\pi j/(2n+1))+4\cos^2(\pi k/(2n+1))\...
T. Amdeberhan's user avatar
4 votes
0 answers
231 views

How distributive are the bad Laver tables?

Suppose that $n\in\omega\setminus\{0\}$. Then define $(S_{n},*)$ to be the algebra where $S_{n}=\{1,...,n\}$ and $*$ is the unique operation on $S_{n}$ where $n*x=x$ $x*1=x+1\,\text{mod}\, n$ and if $...
Joseph Van Name's user avatar
4 votes
1 answer
366 views

Variance of load in maximally loaded bin, if $m$ balls are thrown into $n$ bins

In the paper "Balls and bins a simple and tight analysis" by Raab and Steger, available here strong upper and lower bounds are proved about the number $M$ of balls in a maximally loaded bin when $m$ ...
kodlu's user avatar
  • 10.1k
4 votes
1 answer
1k views

Solving a Diophantine equation related to Algebraic Geometry, Steiner systems and $q$-binomials?

The short version of my question is: 1)For which positive integers $k, n$ is there a solution to the equation $$k(6k+1)=1+q+q^2+\cdots+q^n$$ with $q$ a prime power? 2) For which positive ...
Daniel Litt's user avatar
  • 22.2k
4 votes
2 answers
320 views

How many union-closed families in $\cal{P}(n)$?

A union-closed family $\cal{F} \subseteq \cal{P}([n])$ is a family such that for every $A,B \in \cal{F}$, $A \cup B \in \cal{F}$. Are there any reasonable approximations as to how many such families (...
karpasi's user avatar
  • 706
4 votes
2 answers
388 views

Congruence for complementary Bell numbers

The Bell numbers $B(n)$ can be given as a sum of the (signed) Stirling numbers of the second kind $S(n,k)$ as $B(n)=\sum_{k=0}^nS(n,k)$. There are also the so-called complementary Bell numbers defined ...
T. Amdeberhan's user avatar
4 votes
2 answers
1k views

expected values over binomial distributions

In some works of economics/risk analysis etc., I have seen situations where people take the expected value of a function (such as a utility function/cost function) over a binomial distribution: $$F(n)...
Vipul Naik's user avatar
  • 7,230
4 votes
1 answer
390 views

Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?

Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect? For $k = 2$ the answer is obvious since we can always place circles so that every one of them ...
myro's user avatar
  • 63
4 votes
1 answer
184 views

"JigSaw Puzzle" on Set Family II

I was asked to post a different question following a wording error on my previous question, so here it is. Given a set family $\mathcal{F}$ of $[n]$ (with certain additional properties), such that ...
abacaba's user avatar
  • 364
4 votes
1 answer
324 views

The existence of a specific kind of independent set in a connected graph satisfying the following property

Suppose $G$ is a connected finite graph satisfying that every edge $uv$ of $G$ belongs to a "triangle" $uvw$ such that $uv,uw\in E(G),\ vw\notin E(G)$ or $uv,vw\in E(G),\ uw\notin E(G)$(in other words,...
abcdefg's user avatar
  • 61
4 votes
1 answer
303 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let $G$...
Raghav Kulkarni's user avatar
4 votes
1 answer
291 views

On the real and finite field rank of a $0/1$ matrix - I

Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$. Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
Turbo's user avatar
  • 13.7k
4 votes
0 answers
203 views

Dimension of a certain space of symmetric functions: Part I

Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. A partition $\lambda$ is called a $t$-core if none of its hook lengths are multiples of $t$. QUESTION. Consider the ...
T. Amdeberhan's user avatar
4 votes
2 answers
417 views

Combination power elementary symmetric polynomial inequality

Combine my first previous question and second previous question with the Muirhead inequality. I have posed conjectures of two inequalities as follows: Inequality 1: Let $n>2$ and $1 \le m \le n$...
Đào Thanh Oai's user avatar
4 votes
1 answer
292 views

A Conjecture about the integral related to Chebyshev polynomial

I am interested in the following integral related to the Chebyshev polynomials $$I_{n,m}:= \int_0^\pi \left(\frac {\sin nx}{\sin x}\right)^{m} dx,$$ where $n,m\in \mathbb{Z}^+.$ It is easy to see ...
Jacob.Z.Lee's user avatar
4 votes
0 answers
573 views

A combinatorial bound involving Stirling numbers of the second type

My previous question was solved in a very elegant way, hopefully this (seemingly more complicated) case is also easy for experts. I need the inequality $\Big(\prod^r_{i=1}p_i\Big)\sum^n_{j=0}(-1)^j\...
Dmitry Kerner's user avatar

1
21 22
23
24 25
30