As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
174 views

Reference for a topological result

I am reading the short paper due to Erdös and Bollobás "On a Ramsey-Turán type problem", where they obtain a lower bound for the number of edges on an $n$-graph without $K_4$ as a subgraph ...
Johnny Cage's user avatar
  • 1,453
0 votes
0 answers
116 views

On nilpotent singular $\mathbb F_2^{n\times n}$ matrices

Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$. The set of such singular matrices form a semigroup. The set of nilpotent matrices of size $n\times n$ form a semigroup. ...
Turbo's user avatar
  • 13.2k
6 votes
1 answer
226 views

A Sauer-Shelah-like lermma for prefix tree

I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known. Let $S \subseteq \{0,1\}^n $. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
Or Meir's user avatar
  • 419
0 votes
0 answers
280 views

Union-closed family with a certain property

Now crossposted at math.stackexchange. Consider a union-closed family $\mathcal{F} = \{A_1, \dotsc ,A_n\}$ of $n$ finite sets, $n$ odd, $n \ge 3$, $A_i \neq \emptyset$, $i=1,\dotsc,n$. Let $r=\frac{n+...
BillyJoe's user avatar
  • 234
1 vote
0 answers
54 views

Lower bound for the minimum of the maximum frequency of an element - with restrictions

Consider a family $\mathcal{F}$ of non-empty sets, with $n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$. It is known that of the $\binom{n}{2}$ ways ...
BillyJoe's user avatar
  • 234
4 votes
0 answers
68 views

Bounding the Betti numbers of Čech complexes in Euclidean space

Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \ge 2$. Then let $C=C(S)$ denote the union of closed balls of radius $1$ centered at points of $S$. For $0 \le j \le d-1$, how large can the ...
Matthew Kahle's user avatar
3 votes
0 answers
98 views

Minimum number of couples of sets with non-empty intersection in a union closed family

Every union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, must have at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element ...
BillyJoe's user avatar
  • 234
3 votes
0 answers
67 views

Harper's theorem on the general Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is $$ \min_{S\subseteq ...
Or Meir's user avatar
  • 419
5 votes
1 answer
139 views

Graphs without short cycles and with linear number of edges

Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C_3, C_4, \ldots, C_{f(n)})$-free, i.e. $G$ contains ...
Victor's user avatar
  • 645
9 votes
0 answers
149 views

Number of triangle-free graphs with prescribed number of edges

This question is posted from StackExchange since it received no answer there. Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
abacaba's user avatar
  • 239
3 votes
1 answer
101 views

Bounds for $\mathrm{ex}(n,K_{2,\dots,2}^{(r)})$

$\DeclareMathOperator\ex{ex}$We write $K_{2,\dots,2}^{(r)}$ to denote the $r$-uniform hypergraph with vertex set $\{1,2\}\times\{1,\dots,r\}$ and hyperedge set $\{(1,1),(1,2)\}\times \{(2,1),(2,2)\} \...
Zach Hunter's user avatar
  • 2,322
6 votes
2 answers
367 views

Coloring of a graph representing the power set

For a positive integer $n$, let $\mathcal{P}$ be the power set of $[n]$. Consider the graph $G$ with $\mathcal{P}$ as its vertex set, and, for $S_1,S_2 \in \mathcal{P}$, the edge $(S_1,S_2)$ exists ...
wandering_lambda's user avatar
1 vote
0 answers
88 views

cone structure of complement of hyperplanes

I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes: \begin{cases} (1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\ gy-\sum_{i\in I}x_i+\...
tota's user avatar
  • 575
1 vote
1 answer
105 views

$n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

The coloring game is a game played between Alice and Bob. There exists a grid of size $n \times n$, where $n$ is a strictly positive integer. Each cell of the grid can be colored with a color that ...
pierreciv's user avatar
4 votes
1 answer
145 views

Extremal problems in additive combinatorics (over finite fields)

As you may know, there has been very recently a big breakthrough concerning upper bounds for the capset problem over $\mathbb{F}_3^n$ (and further generalizations to $\mathbb{F}_q^n$). I was wondering ...
Johnny Cage's user avatar
  • 1,453
25 votes
3 answers
823 views

What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple ...
a3nm's user avatar
  • 421
1 vote
1 answer
118 views

Chromatic number or independence number of the generalized Kneser Graph

For positive integers $n,k$ and $s$, where $0\le s<k$ and $k \le n$, we define the generalized Kneser graph $K(n,k,s)$ as follows: The vertices of $K(n,k,s)$ are the $k$-subsets of $[2n]$, i.e., we ...
wandering_lambda's user avatar
3 votes
1 answer
483 views

Sum of $q$-binomial coefficients

Denote by $ \binom{n}{k}_q = \prod_{i=0}^{k-1} \frac{ q^{n-i} - 1 }{ q^{k-i} - 1 } $, $ k = 0, 1, \ldots, n $, the $ q $-binomial (Gaussian) coefficients. These numbers are symmetric, in the sense ...
aleph's user avatar
  • 445
5 votes
2 answers
350 views

Counting intersections of hyperplanes

This is a dublicate from stackexchange: Consider two families of hyperplanes $F_1$ and $F_2$ in $\mathbb{R}^d$ both containing $n$ hyperplanes. We have that for all $f \in F_1$ and $g \in F_2$ that $f$...
Peter K's user avatar
  • 153
1 vote
0 answers
115 views

Probability puzzle on partitions

Consider a set $U$ of size $n$ and let $\mathcal{S}$ be the set of all $(n/2)$-subsets of $U$ (assume $n$ is divisible by 4). Let $P$ be a partition of $\mathcal{S}$ into $k$ blocks $B_1,\dots,B_k$. ...
ARQ's user avatar
  • 11
4 votes
0 answers
141 views

Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?

This is not a concrete question, just some thoughts. The Komlos Conjecture is as follows- There exists an absolute constant $C>0$, such that the following holds: For all $d$ and any set of vectors ...
Sudipta Roy's user avatar
1 vote
0 answers
99 views

Number of intersections that must occur in any partition of a given size

Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$. Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of ...
wandering_academic's user avatar
3 votes
0 answers
87 views

Minimum number of partitions of a set such that the same pair must occur in a block in at least half of them

For positive integers $k$ and $n$, let ${S} = \{1,\dots,k\ n\}$. Consider $\ell \ge 3$ partitions $P_1,\dots,P_\ell$ of ${S}$, where each $P_i$ splits ${S}$ into $n$ blocks all of size $k$. Question: ...
Arun's user avatar
  • 31
3 votes
2 answers
246 views

Ramsey-Turán density function is well defined

Define $$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$ and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as $$f_l(\alpha)=\lim_{n\to \infty}...
JPMarciano's user avatar
0 votes
1 answer
123 views

A general Turan-like question

Thinking of an edge as of a $2$-clique, it's natural to consider a slightly more general question than Turan considered in his celebrated theorem: given $r \le k \le n$, what is the maximal possible ...
Danil Akhtiamov's user avatar
2 votes
1 answer
167 views

Maximizing and minimizing the number of positive product $k$-subsets of an $n$-set

The question is simple but require some definitions. I came across resolving a certain inequality. If there is no closed answer is there a related sequence describing the situation? Let $$S\ :=\ \{X=...
Toni Mhax's user avatar
  • 620
8 votes
2 answers
784 views

a Littlewood–Offord-type problem concerning the "cubical lattice"

Fix even $n$ and consider the boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, $f : (x_0, \ldots , x_{n - 1}) \mapsto (x_0 \vee x_1) \wedge (x_2 \vee x_3) \wedge \cdots \wedge (x_{n - 2} \vee ...
BD107's user avatar
  • 61
3 votes
1 answer
169 views

Products of Mersenne numbers as sums of real numbers

A Mersenne number is a number of the form $2^k-1$ for some $k \in \mathbb{N}$. Consider the set of $2^n-1$ products of Mersenne numbers $$M_n=\left\{ \prod_{k\in S} (2^k-1) : S \subseteq [n], S\neq \...
Ben's user avatar
  • 898
7 votes
1 answer
474 views

Packing equal-size disks in a unit disk

Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...
Hao's user avatar
  • 581
1 vote
0 answers
38 views

Inequality between union-closed families of sets and corresponding upward-closed families

This question is about an inequality for union-closed families of sets related to Frankl's conjecture and a result by Reimer. It relates the union-closed families and corresponding upward-closed ...
Steve's user avatar
  • 1,055
4 votes
3 answers
504 views

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
Yungchen Jen's user avatar
1 vote
1 answer
129 views

Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$

Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square. Through the determinant ...
Turbo's user avatar
  • 13.2k
3 votes
1 answer
172 views

Maximum number of subsets in which people co-exist with their friends

Let $P = \{1,\dots,p\}$ be a set of people. Consider partitioning $P$ into two disjoint sets, $A$ (of cardinality $a$) and $A^c = P-A$. Let us index $A$ as $A = \{A_1,\dots,A_a\}$. Each person in $A$ ...
mgus's user avatar
  • 143
12 votes
1 answer
184 views

Ternary sequences satisfying $ x_i + y_i = 1 $ for some $ i $

Consider a set of strings $ {\mathcal S} \subset \{0, 1, 2\}^n $ satisfying the following two conditions: 1.) every string in $ {\mathcal S} $ has exactly $ k $ symbols from $ \{0, 1\} $ (i.e., $ \...
aleph's user avatar
  • 445
3 votes
2 answers
116 views

For $n$ different sets whose union has size $n+1$ ,can you remove the same point from each set while retaining their difference

Let $(A_i)_{i=1}^{n}$ be $n$ different sets. Say $Z := \bigcup_{i=1}^{n}A_i$. Q1: Is it true that if $|Z| \gt n$ then you can find $x \in Z$ such that the $(A_i-{x)}$ are still all different? Q2: If $|...
Jérôme JEAN-CHARLES's user avatar
6 votes
1 answer
232 views

Permutation function based on subsets

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$ in $\sigma$ ...
pi66's user avatar
  • 1,189
5 votes
1 answer
164 views

Minimum number of independent pairs in a matroid

Given a matroid $M$ with ground set $E$ of size $2n$, suppose there exists $A\subseteq E$ of size $n$ such that both $A$ and $E\setminus A$ are independent. What is the minimum number of $B\subseteq E$...
TZM's user avatar
  • 143
5 votes
0 answers
122 views

Exponential bound for very weak sunflowers?

Call $r$ sets diverse if for every $0\le i\le r$ there is an element contained in exactly $i$ of them. A family of sets is r-diverse if any $r$ of its members are diverse. Is there for every $r\ge 3$ ...
domotorp's user avatar
  • 18k
7 votes
0 answers
160 views

Szemerédi's regularity lemma for binary operations

Szemerédi's regularity lemma is an approximate structure theorem for all large graphs (symmetric binary relations). There are versions for multicolored graphs and directed graphs. Is there an ...
Richard Stanley's user avatar
6 votes
0 answers
105 views

A question related to the union-closed sets conjecture

Let $f(n)$ denote the maximum possible cardinality of a collection $\mathcal F$ of nonempty sets which is closed under unions ($X,Y\in\mathcal F\implies X\cup Y\in\mathcal F$) and is such that no ...
bof's user avatar
  • 9,539
2 votes
1 answer
90 views

Computation of cyclic van der Waerden numbers

Van der Waerden's theorem gives us a finite number $W(k,r)$ defined as the smallest positive integer $N$ such that for any $n\geq N$, any $r$-coloring of $[n]=\{1,\dots,n\}$ admits a monochromatic $k$-...
Tristan Shin's user avatar
3 votes
0 answers
69 views

Boundary differences in two graphs

Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
H A Helfgott's user avatar
  • 18.6k
2 votes
1 answer
272 views

Do sparse graphs contain a single regular pair?

An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...
alpmu's user avatar
  • 785
4 votes
0 answers
94 views

Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ...
Antoine Labelle's user avatar
1 vote
1 answer
106 views

Schur triples question

So I've been reading through On the number of monochromatic Schur triples by Datrovsky on finding the minimal number of Schur triples. This means you're trying to 2-colour the set of the smallest n ...
Jonathan Kariv's user avatar
5 votes
1 answer
262 views

Size of a family of sets of $k$-separated functions over $\{0,1,\ldots,n-1\}$

For $n\ge 1$ we write $[n]$ to denote the set $\{0,1,\ldots,n-1\}$. Let $2^{[n]}$ be the set of all functions from $[n]$ to $\{0,1\}$. Let $\mathcal{F}$ and $\mathcal{G}$ be two nonempty subsets of $2^...
Dominik Kwietniak's user avatar
1 vote
0 answers
68 views

4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs. The main purpose of the paper is to show ...
Johnny Cage's user avatar
  • 1,453
0 votes
1 answer
54 views

Maximal families of equal length intervals consist of equilateral triangles

My question is a follow up to How to find n points on a plane so that as many pair of points as possible have the same distance? -- see the conjecture at the bottom of this post. Let $\ n\ $ be a ...
Wlod AA's user avatar
  • 4,315
1 vote
1 answer
73 views

What is the minimal possible size of a subset of this semigroup satisfying the following conditions?

Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities: $\forall a \in P[A]$ ...
Chain Markov's user avatar
  • 2,618
2 votes
0 answers
109 views

How many edges can be in an unbalanced bipartite graph of girth $>6$?

Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$. There is a simple counting argument called the Moore Bounds that gives $$|E| = O\...
GMB's user avatar
  • 1,369