20

In the comments to the question, I notice something which might be an error, or at least is an incomplete response. It is pointed out in the comments that there exist nonisomorphic groups with isomorphic subgroup lattices. While true, that fact doesn't answer this question, since it is possible to have isomorphic subgroup lattices and nonisomorphic subgroup ...

11

For large prime $p$, there are uncountably many non-isomorphic Tarski monsters of exponent $p$.
For these groups $G$, the subgroups lattice consists of basically a partition of $G\smallsetminus\{1\}$ into countably many subsets of cardinal $p-1$ (so the subgroups are the whole group, $\{1\}$ and the union of $\{1\}$ with any component of the partition. ...

11

The answer is no. Let $\kappa$ be any infinite cardinal, regular or singular, and assume for a contradiction that there is a set $E\subseteq\mathcal P(\kappa)$ satisfying your conditions. I will call the elements of $\kappa$ points and the elements of $E$ lines.
The lines do not all go through one point: Given a point $\alpha$, choose a point $\beta\ne\alpha$...

10

The answer is no.
A space is called resolvable if it contains two disjoint dense subspaces. Clearly $X$ is resolvable if and only if $\chi(X)=2$. Lets prove by induction on $n \geq 2$ that if $\chi(X) \leq n$ then $X$ is resolvable (and hence $\chi(X)=2$).
The base case $n=2$ is clear so suppose there is a coloring $f:X \to n+1$. Let $V$ be the union of ...

answered Jan 30 '19 at 22:12

Ramiro de la Vega

10.9k11 gold badge3939 silver badges5151 bronze badges

9

Update. Here is a new simpler answer that works for all regular
$\kappa$, including $\kappa=\omega$. And I have omitted the use
of Fodor's lemma, using instead merely the pigeon-hole principle.
Suppose that $\kappa$ is infinite and we have a projective plane on
$\kappa$ many points, with all lines of size less than $\kappa$.
Since there are $\kappa$ many ...

answered Dec 3 '17 at 16:13

Joel David Hamkins

193k3333 gold badges595595 silver badges10431043 bronze badges

9

Partition $\omega$ into three infinite subsets $A_0,A_1,A_2$. Let $S$ consists of subsets which intersects precisely two of the $A_i$ at infinitely many elements. It can obviously be $3$-colored. Suppose there was a $2$-coloring, with color classes $c_0,c_1$. Then either $c_0$ or $c_1$ contains infinitely many elements of some two of $A_0,A_1,A_2$, say $c_0\...

9

It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are the $p^3$ general position planes, with $p^2$ planes through each point. There are no 3 collinear points if the surface is chosen appropriately, so for any 3 ...

co.combinatorics oc.optimization-and-control combinatorial-optimization infinite-combinatorics hypergraph

9

It is continuum. The coloring with continuum many colors is clear (all points may have different color). Assume that we have $\kappa<c$ colors. Consider the Cantor set $K$. All its subsets are Lebesgue measurable. If some color contains uncountably many points from $K$, it constitutes a monochromatic edge. So, each color contains at most $\omega$ points ...

answered Apr 21 '21 at 11:47

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

8

Yes, your conjecture is true.
Suppose otherwise. Then there exists a counterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f(X) = 1$.
There are $5440$ different choices of the tuple $(A, B, C) \in \mathcal{P}(8)^3$ satisfying your constraints. For each such tuple, we obtain two ...

answered Feb 19 '18 at 17:11

Adam P. Goucher

11.4k22 gold badges4848 silver badges9292 bronze badges

8

As explained in a previous MO question, there is no unique generalization of the eigenvalue of an $n\times n$ matrix to an $n\times n\times n$ tensor. One approach is to construct a higher-order singular value decomposition. This has been worked out for the specific case of $2\times 2\times 2$ tensors by Ana Rovi in a M.Sc. thesis. Even for this simple case, ...

answered May 12 '20 at 11:43

Carlo Beenakker

139k1212 gold badges334334 silver badges482482 bronze badges

7

An elementary counting argument shows that $2$-$(v,3,3)$ exists only if $v$ is odd (or, more precisely, for $\lambda \equiv 3 \pmod{6}$ a $2$-$(v,3,\lambda)$ exists only if $v \equiv 1 \pmod{2}$). This necessary condition is sufficient.
Arguably the simplest direct construction for the case $\lambda = 3$ that covers all odd $v$ is to use commutative ...

answered Dec 10 '13 at 16:33

Yuichiro Fujiwara

3,58211 gold badge2222 silver badges4242 bronze badges

7

The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.
More precisely, he shows that
$$ 2\left\lceil \frac{k}{3}\right\rceil \left\lfloor \frac{2k}{3}\right\rfloor^2 < m(k) \leq \binom{2k+1}{3}$$
where the implied constants ...

7

Others have already answered, but I think the following counting argument is worth pointing out:
there are $2^{2^{\aleph_0}}$ hypergraphs on $\omega$ (since a hypergraph on $\omega$ is just a collection of nonempty subsets of $\omega$),
each isomorphism class contains at most $2^{\aleph_0}$ elements (since there are that many permutations of $\omega$),
so ...

7

This is essentially done by the Bernstein set construction: if one has $\kappa$ many sets each of size $\kappa$, then order them into ordinal $\kappa$ and recursively choose 2 points from each, so that all these points are distinct. That is, we have $x_\alpha,y_\alpha\in A_\alpha$ with all $x_\alpha,y_\alpha$ distinct. At the end, color each $x_\alpha$ red, ...

7

No, there isn't. This is essentially the dual version of the De Bruijn-Erdos theorem if the elements of $\mathcal C$ are the points, and the elements from $\{1,\ldots,n\}$ are the lines. The original proof is here.

6

The case $s=1$ is Erdős hypergraph mathcing conjecture from
Paul Erdős (1965). A problem on independent $r$-tuples. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95.
users.renyi.hu/~p_erdos/1965-01.pdf
A recent paper about it is
Peter Frankl (2017) Proof of the Erdős matching conjecture in a new range, Israel Journal of Mathematics 222(1), pp ...

answered Apr 7 '18 at 1:46

Thomas Kalinowski

2,88622 gold badges1515 silver badges2222 bronze badges

6

The intersecting family in your example has $\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$ members by Sperner's theorem. An example that achieves a larger value would be to take all the subsets of $[n]$ that have $1+\lfloor \frac{n}{2}\rfloor$ elements. This is best possible.
Milner proved that the largest size of a $k$-intersecting antichain in $\mathcal P([n])...

answered May 2 '18 at 9:15

Gjergji Zaimi

81.2k44 gold badges212212 silver badges380380 bronze badges

6

As @Keith Kearnes says, the negative answer ought to be somewhere in Roland Schmidt's book. Unless I'm mistaken, it suffices to find two non isomorphic groups with isomorphic coset lattices. Indeed, the elements of $G$ correspond directly with the cosets of the trivial subgroup. By applying the regular group action, you can take any such element (or 1-...

6

Observe that $|\mathcal L|\leq\lambda$, since mapping $k$ to the pair of its two smallest elements gives an injection $\mathcal L\to\lambda^2$.
Enumerate elements of $\mathcal L$ as $k_\alpha,\alpha<\lambda$. Then we can define by transfinite recursion $f(k_\alpha)$ to be the least element of $k_\alpha$ distinct from $f(k_\beta),\beta<\alpha$.

6

In general no. Partition the vertices onto $n/k$ subsets (I call them classes) of size $k$, where $k$ grows as $n^{2/3}$. Take into your hypergraph all 4-edges with the vertices in the same class. It has about $(n/k)k^4=nk^3\sim n^3$ edges, but each independent set contains at most $3$ vertices from each class, thus $O(n^{1/3})$ vertices.
Well, your graph ...

answered Jun 23 '19 at 13:38

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

6

This is Baranyai's theorem. Other than in Baranyai's original paper you can also find a cool proof in the article "Uniform hypergraphs" by Brouwer and Schrijver which uses max-flow min-cut.

answered Aug 22 '20 at 21:26

Gjergji Zaimi

81.2k44 gold badges212212 silver badges380380 bronze badges

6

I will turn my comment above into a self-contained answer. Given a hypergraph $H=(V,E)$ and $X \subseteq V$, we say that $X$ is shattered if for all $X' \subseteq X$, there exists $e \in E$ such that $e \cap X=X'$. The VC dimension of $H$ is the size of a largest shattered set. Given a finite dimensional vector space $\mathbb V$, let $H$ be the hypergraph ...

6

The cardinals $\bf k_n$ ($2\le n\lt\omega$) are all equal.
Lemma. Let $\kappa$ be an infinite cardinal. Given a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt n$, we can construct a set $B\subseteq[\omega]^\omega$ with $|B|=\kappa$ and $\chi(\omega,B)\gt n^2$.
Proof. For each $a\in A$ choose a collection $B_a\subseteq[a]^\omega$ so ...

6

I will show, with some non-rigorous steps, that a bound of this form that is valid for arbitrary tensors and useful for sparse tensors (fewer than $n^{k/2}$ nonvanishing entries) does not exist.
First note that there is a problem with using the $\ell^2$ norm to define the spectral norm for very sparse tensors $A$, regardless of how you try to bound it. The ...

6

Let $m$ be chosen later, and let $A_1, A_2, \dots, A_n$ be independently chosen random subsets of $\{1,2,\dots m\}$, each having size $n$.
For a fixed $a+1$-tuple $(x_1, x_2, \dots, x_{a+1})$ of distinct elements from $\{1,\dots,m\}$, and a fixed triple $(i,j,k)$, the probability that $\{x_1, \dots, x_a\} \subseteq A_i \cap A_j \cap A_k$ is at most $\left(\...

co.combinatorics oc.optimization-and-control combinatorial-optimization infinite-combinatorics hypergraph

answered Apr 22 '21 at 2:57

Kevin P. Costello

5,50122 gold badges2424 silver badges3535 bronze badges

5

Here is my intuition that it may not be possible.
I am guessing that as in the case of the original LLL, such an inequality would in turn imply a simpler inequality of the following form:
"If the dependency graph is $d$-degenerate and every event has probability at most $p$ and $4pd<1$,
then we can avoid all events".
But this latter statement appears ...

5

Here is another way of thinking about the problem. Suppose for simplicity that your hypergraph $\mathcal{H}$ has exactly $|V(\mathcal{H})|$ hyperedges (as was mentioned by Dominic, we can immediately exclude any hypergraph with more hyperedges).
Let $G'$ be a bipartite graph where both parts are of size $|V(\mathcal{H})|$. We associate the left side of $G'$...

5

Yes. Let $S$ be a family of finite subsets of some linearly ordered set $L.$ Suppose that each member of $S$ has at least two elements, and that no two members of $S$ form a "globally ordered pair". Then we can color every element of $L$ red or blue so that, for each $X\in S,$ the top element of $X$ is red and the bottom element of $X$ is blue.

5

This is equivalent reformulation of Erdös-Faber-Lovász conjecture, see Wikipedia page about it.
https://en.m.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture

answered Jan 12 '16 at 16:03

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

5

Yes, and we do not even use the restrictions on mutual intersections of edges. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices (possibly we get the same edge several times). It remains to properly color a graph with $n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of ...

answered Nov 27 '17 at 8:13

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

hypergraph × 218co.combinatorics × 118

graph-theory × 80

infinite-combinatorics × 56

graph-colorings × 44

set-theory × 39

matching-theory × 15

reference-request × 13

algorithms × 11

linear-algebra × 9

pr.probability × 8

perfect-matchings × 8

lo.logic × 6

random-graphs × 6

combinatorial-designs × 6

covering × 5

discrepancy-theory × 5

gn.general-topology × 4

computational-complexity × 4

ct.category-theory × 3

projective-geometry × 3

order-theory × 3

simplicial-complexes × 3

ramsey-theory × 3

extremal-graph-theory × 3