Zobrazeno 1 - 10
of 139
pro vyhledávání: '"Salia, Nika"'
Autor:
Salia, Nika, Tóth, Dávid
This paper establishes an analog of the Erd\H{o}s-Ko-Rado theorem to polynomial rings over finite fields, affirmatively answering a conjecture of C. Tompkins. A $k$-uniform family of subsets of a set of finite size $n$ is $l$-intersecting if any two
Externí odkaz:
http://arxiv.org/abs/2409.17821
Autor:
Cambie, Stijn, Salia, Nika
Erd\H{o}s and S\'os initiated the study of the maximum size of a $k$-uniform set system, for $k \geq 4$, with no singleton intersections $50$ years ago. In this work, we investigate the dual problem: finding the minimum size of a $k$-uniform hypergra
Externí odkaz:
http://arxiv.org/abs/2408.16758
Autor:
Clifton, Alexander, Salia, Nika
In this work, we study how far one can deviate from optimal behavior when embedding a planar graph. For a planar graph $G$, we say that a plane subgraph $H\subseteq G$ is a \textit{plane-saturated subgraph} if adding any edge (possibly with new verti
Externí odkaz:
http://arxiv.org/abs/2403.02458
Bollob\'as proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of
Externí odkaz:
http://arxiv.org/abs/2312.09999
Chung and Graham considered the problem of minimizing the number of edges in an $n$-vertex graph containing all $n$-vertex trees as a subgraph. They showed that such a graph has at least $\frac{1}{2}n \log{n}$ edges. In this note, we improve this low
Externí odkaz:
http://arxiv.org/abs/2311.01488
An independent vertex subset $S$ of the directed graph $G$ is a kernel if the set of out-neighbors of $S$ is $V(G)\setminus S$. An independent vertex subset $Q$ of $G$ is a quasi-kernel if the union of the first and second out-neighbors contains $V(G
Externí odkaz:
http://arxiv.org/abs/2307.04112
The Erd\H{o}s-S\'os conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patk\'os, and
Externí odkaz:
http://arxiv.org/abs/2303.10400
The Wiener index of a (hyper)graph is calculated by summing up the distances between all pairs of vertices. We determine the maximum possible Wiener index of a connected $n$-vertex $k$-uniform hypergraph and characterize for every~$n$ all hypergraphs
Externí odkaz:
http://arxiv.org/abs/2302.08686
In this work, we give the sharp upper bound for the number of cliques in graphs with bounded odd circumferences. This generalized Tur\'an-type result is an extension of the celebrated Erd\H{o}s and Gallai theorem and a strengthening of Luo's recent r
Externí odkaz:
http://arxiv.org/abs/2212.01989
Autor:
Győri, Ervin, Salia, Nika
Extensions of Erd\H{o}s-Gallai Theorem for general hypergraphs are well studied. In this work, we prove the extension of Erd\H{o}s-Gallai Theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an $n$-vertex $3$-unifor
Externí odkaz:
http://arxiv.org/abs/2211.16184