Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
34 views

The linear embedding complexity of subsets of $0/1$ cube

We say $\pi$ is a subset of the $0/1$ integer points in $t$ dimensions represented by coordinates $(x_1,\dots,x_t)$ of complexity $\log^ct$ if there is an $A$ of $2^{\log^ct}\times2^{\log^ct}$ ...
7
votes
1answer
422 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 ...
1
vote
0answers
18 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 ...
2
votes
0answers
45 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 ...
1
vote
1answer
48 views

Schur Complement and depermuting an algorithm for determinant modulo $2$

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

On a $(k,l)$-monochromatic Hamming distance in $\mathbb F_2$?

A $(k,l)$-monochromatic edit on a matrix $M\in\mathbb F_2^{n\times n}$ is the operation $$M+A$$ where $A\in\mathbb F_2^{n\times n}$ is of rank $1$ and number of $1$'s in $A$ is $kl$ and there are $l$ ...
3
votes
1answer
122 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$ ...
0
votes
0answers
75 views

Good source for understanding shifting techniques in combinatorics

There are many theorems in extremal combinatorics (e.g. the Erdos-Ko-Rado theorem, the Kruskal-Katona theorem) that can be proved via "shifting" arguments. See for example the following ...
12
votes
1answer
171 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., $ \...
3
votes
2answers
105 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 $|...
6
votes
1answer
214 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$ ...
5
votes
1answer
145 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$...
5
votes
0answers
108 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$ ...
7
votes
0answers
141 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 ...
6
votes
0answers
92 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 ...
2
votes
1answer
62 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$-...
3
votes
0answers
66 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 ...
2
votes
0answers
172 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 ...
4
votes
0answers
82 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 ...
1
vote
1answer
85 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 ...
5
votes
1answer
246 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^...
1
vote
0answers
47 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 ...
0
votes
1answer
52 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 ...
1
vote
1answer
70 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]$ ...
2
votes
0answers
45 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\...
4
votes
1answer
152 views

Complementing the red and blue boolean cube?

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations? ...
1
vote
0answers
36 views

Partition complexity measure of the boolean cube?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the ...
1
vote
0answers
81 views

Maximum number of ways of splitting a set of points with an hyperplane

Given a set $S$ of $n$ points in $\mathbb{R}^d$, let $D_S$ be the set $\{\mathbf{v}=|\mathbf{u}-\mathbf{u'}|: \mathbf{u},\mathbf{u'}\in S\}$ (where $\forall i=1,2,\ldots, d$, $\mathbf{v}_i=|\mathbf{u}...
2
votes
0answers
182 views

The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...
1
vote
0answers
20 views

Do small subsets of $S_n$ subgroups cover almost all permutation configurations of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$. For ...
1
vote
0answers
91 views

Are almost all permutation configurations from $S_n$ covered by small subsets subgroups of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$. Do we have ...
33
votes
4answers
1k views

Dividing a cake between $n-1$, $n$, or $n+1$ guests

A housewife is waiting for guests and has prepared a cake. She doesn't know how many guests will come, but it will be $n-1$, $n$, or $n+1$. What is the minimal number $f(n)$ of pieces the cake ...
5
votes
2answers
792 views

Cardinality of certain subsets in vector spaces over finite fields

Assume that you have an $n$-dimensional vector space over a finite field (therefore the number of elements in the vector space is finite) and $F$ is a subset of this vector space which contains $m$ ...
1
vote
0answers
59 views

Polytopes that can be efficiently described and efficiently covered by cubes or simplices?

Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...
2
votes
0answers
63 views

Restricted Erdos-Ko-Rado theorem reference

Consider a family $\mathfrak{F}$ of $k$ element subsets of $\{1,2,..,n\}$, where $n\geq 2k$, such that any two members of $\mathfrak{F}$ have nonempty intersection. The Erdos-Ko-Rado theorem asserts ...
4
votes
0answers
139 views

Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles

Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...
6
votes
1answer
225 views

An inequality for rearrangement-style sums

The following is a holdover from my math contest days that I never got around to solve. We will use the notation $\left[ k\right] $ for the set $\left\{ 1,2,\ldots,k\right\} $ whenever $k$ is a ...
7
votes
1answer
379 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 ...
3
votes
1answer
107 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 ...
4
votes
0answers
88 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
0answers
96 views

Number of $b$-separated Sidon sets with pairwise difference set intersection bounds

Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ call a set of $m$ integers $a_1<\dots<a_m$ in the interval $(p^\alpha,p-p^\alpha)$ to be $b$-separated Sidon if: $a_i-a_j\...
4
votes
2answers
358 views

An extremal combinatorics problem

Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ what is the largest $m$ we have such that in the interval $(p^\alpha,p-p^\alpha)$ there are $m$ integers $a_1<\dots<a_m$ ...
2
votes
0answers
50 views

Is the finite projective plane stable as an extremal set system?

Let $\Sigma$ be a set of $|\Sigma| = n$ subsets of the universe $[n]$, each of size $k$, with the property that any two of these subsets intersect on at most one element. It is easy to see that the ...
2
votes
1answer
119 views

Distinguishing points by sets of given size

The problem is: Given a finite set $X$ with size $x$ and let $B$ denote a family of $k$-element subsets of $X$, called blocks. What is the smallest possible number $n$ of blocks such that every ...
3
votes
0answers
89 views

chromatic number of plane using Cairo pentagonal tiling

Scale the Cairo pentagonal tiling so the short side is of length 1. Then it is easy to colour the tiling with 8 colours, two parallel ribbons of four colours each, to establish that the chromatic ...
20
votes
0answers
375 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
1
vote
2answers
161 views

Extremal density of a graph without a non-backtracking $2k$-cycle

The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form $$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$ while the ...
8
votes
1answer
261 views

A generalization of Erdős-Ko-Rado theorem

Is there any result known about the following generalization of the Erdős-Ko-Rado theorem? Let $n, k, r, s$ be positive integers. We call a family $\mathcal{F}$ of $k$-element subsets of $\{1,\ldots, ...
2
votes
1answer
71 views

If we take a small subset of a sparse/uniform set system, how uniform can we arrange for the subset to be?

Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements ...
1
vote
1answer
113 views

Number of distinct 3-sets formed as subsets of a 4-uniform set family

Let $\mathcal{F} \subseteq \binom{[n]}{4}$ be a collection of size-4 subsets of $\{1,\ldots,n\}$, i.e., a 4-uniform set family. Let $\mathcal{F'}$ be the collection of size-3 sets for which a ...