Log in

Relevant bibliographies by topics / Extremal hypergraph theory / Journal articles

Journal articles on the topic 'Extremal hypergraph theory'

To see the other types of publications on this topic, follow the link: Extremal hypergraph theory.

Author: Grafiati

Published: 10 December 2022

Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 49 journal articles for your research on the topic 'Extremal hypergraph theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

CUTLER, JONATHAN, and A. J. RADCLIFFE. "Hypergraph Independent Sets." Combinatorics, Probability and Computing 22, no. 1 (October 11, 2012): 9–20. http://dx.doi.org/10.1017/s0963548312000454.

Full text

Abstract:

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices isj-independentif its intersection with any edge has size strictly less thanj. The Kruskal–Katona theorem implies that in anr-uniform hypergraph with a fixed size and order, the hypergraph with the mostr-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number ofj-independent sets in anr-uniform hypergraph.

APA, Harvard, Vancouver, ISO, and other styles

2

Wang, Yanna, and Bo Zhou. "Extremal properties of the distance spectral radius of hypergraphs." Electronic Journal of Linear Algebra 36, no. 36 (July 8, 2020): 411–29. http://dx.doi.org/10.13001/ela.2020.5121.

Full text

Abstract:

The distance spectral radius of a connected hypergraph is the largest eigenvalue of its distance matrix. The unique hypertrees with minimum distance spectral radii are determined in the class of hypertrees of given diameter, in the class of hypertrees of given matching number, and in the class of non-hyperstar-like hypertrees, respectively. The unique hypergraphs with minimum and second minimum distance spectral radii are determined in the class of unicylic hypergraphs. The unique hypertree with maximum distance spectral radius is determined in the class of $k$-th power hypertrees of given matching number.

APA, Harvard, Vancouver, ISO, and other styles

3

Fang, Lusheng, Bo Deng, Haixing Zhao, and Xiaoyun Lv. "Graph Entropy Based on Strong Coloring of Uniform Hypergraphs." Axioms 11, no. 1 (December 22, 2021): 3. http://dx.doi.org/10.3390/axioms11010003.

Full text

Abstract:

The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph. Then, we define the graph entropy based on the vertex strong coloring of a hypergraph. Moreover, some tightly upper and lower bounds of such graph entropies as well as the corresponding extremal hypergraphs are obtained.

APA, Harvard, Vancouver, ISO, and other styles

4

Hu, Sinan, and Biao Wu. "A Note on the Lagrangian of Linear 3-Uniform Hypergraphs." Symmetry 14, no. 7 (July 7, 2022): 1402. http://dx.doi.org/10.3390/sym14071402.

Full text

Abstract:

Lots of symmetric properties are well-explored and analyzed in extremal graph theory, such as the well-known symmetrization operation in the Turán problem and the high symmetric in the extremal graphs. This paper is devoted to studying the Lagrangian of hypergraphs, which connects to a very symmetric function—the Lagrangian function. Given an r-uniform hypergraph F, the Lagrangian density πλ(F) is the limit supremum of r!λ(G) over all F-free G, where λ(G) is the Lagrangian of G. An r-uniform hypergraph F is called λ-perfect if πλ(F) equals r!λ(Kv(F)−1r). Yan and Peng conjectured that: for integer r≥3, there exists n0(r) such that if G and H are two λ-perfect r-graphs with |V(G)| and |V(H)| no less than n0(r), then the disjoint union of G and H is λ-perfect. Let St denote a 3-uniform hypergraph with t edges {e1,⋯,et} satisfying that ei∩ej={v} for all 1≤i<j≤t. In this paper, we show that the conjecture holds for G=S2 and H=St for all t≥62. Moreover, our result yields a class of Turán densities of 3-uniform hypergraphs. In our proof, we use some new techniques to study Lagrangian density problems; using a result of Sidorenko to find subgraphs, and a result of Talbot to upper bound the Lagrangian of a hypergraph.

APA, Harvard, Vancouver, ISO, and other styles

5

Ferber, Asaf, and Asaf Shapira. "A quantitative Lovász criterion for Property B." Combinatorics, Probability and Computing 29, no. 6 (August 7, 2020): 956–60. http://dx.doi.org/10.1017/s0963548320000334.

Full text

Abstract:

AbstractA well-known observation of Lovász is that if a hypergraph is not 2-colourable, then at least one pair of its edges intersect at a single vertex. In this short paper we consider the quantitative version of Lovász’s criterion. That is, we ask how many pairs of edges intersecting at a single vertex should belong to a non-2-colourable n-uniform hypergraph. Our main result is an exact answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollobás’s two families theorem with Pluhar’s randomized colouring algorithm.

APA, Harvard, Vancouver, ISO, and other styles

6

Mubayi, Dhruv, and Oleg Pikhurko. "Constructions of non-principal families in extremal hypergraph theory." Discrete Mathematics 308, no. 19 (October 2008): 4430–34. http://dx.doi.org/10.1016/j.disc.2007.08.040.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

BALOGH, JÓZSEF, JANE BUTTERFIELD, PING HU, JOHN LENZ, and DHRUV MUBAYI. "On the Chromatic Thresholds of Hypergraphs." Combinatorics, Probability and Computing 25, no. 2 (March 6, 2015): 172–212. http://dx.doi.org/10.1017/s0963548315000061.

Full text

Abstract:

Let $\mathcal{F}$ be a family of r-uniform hypergraphs. The chromatic threshold of $\mathcal{F}$ is the infimum of all non-negative reals c such that the subfamily of $\mathcal{F}$ comprising hypergraphs H with minimum degree at least $c \binom{| V(H) |}{r-1}$ has bounded chromatic number. This parameter has a long history for graphs (r = 2), and in this paper we begin its systematic study for hypergraphs.Łuczak and Thomassé recently proved that the chromatic threshold of the so-called near bipartite graphs is zero, and our main contribution is to generalize this result to r-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Turán number is achieved uniquely by the complete (r + 1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of non-degenerate hypergraphs whose Turán number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {abc, abd, cde}, the so-called generalized triangle.In order to prove upper bounds we introduce the concept of fibre bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fibre bundle dimension, a structural property of fibre bundles that is based on the idea of Vapnik–Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemerédi for graphs and might be of independent interest. Many open problems remain.

APA, Harvard, Vancouver, ISO, and other styles

8

Keller, Nathan, and Noam Lifshitz. "The Junta Method in Extremal Hypergraph Theory and Chvátal's Conjecture." Electronic Notes in Discrete Mathematics 61 (August 2017): 711–17. http://dx.doi.org/10.1016/j.endm.2017.07.027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Ahlswede, Rudolf, and Ning Cai. "On Extremal Set Partitions in Cartesian Product Spaces." Combinatorics, Probability and Computing 2, no. 3 (September 1993): 211–20. http://dx.doi.org/10.1017/s0963548300000626.

Full text

Abstract:

The partition number of a product hypergraph is introduced as the minimal size of a partition of its vertex set into sets that are edges. This number is shown to be multiplicative if all factors are graphs with all loops included.

APA, Harvard, Vancouver, ISO, and other styles

10

Ferber, Asaf, Gweneth McKinley, and Wojciech Samotij. "Supersaturated Sparse Graphs and Hypergraphs." International Mathematics Research Notices 2020, no. 2 (March 8, 2018): 378–402. http://dx.doi.org/10.1093/imrn/rny030.

Full text

Abstract:

Abstract A central problem in extremal graph theory is to estimate, for a given graph H, the number of H-free graphs on a given set of n vertices. In the case when H is not bipartite, Erd̋s, Frankl, and Rödl proved that there are 2(1+o(1))ex(n, H) such graphs. In the bipartite case, however, bounds of the form 2O(ex(n, H)) have been proven only for relatively few special graphs H. As a 1st attempt at addressing this problem in full generality, we show that such a bound follows merely from a rather natural assumption on the growth rate of n ↦ ex(n, H); an analogous statement remains true when H is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of Erd̋s and Simonovits. The bounds on the number of H-free hypergraphs are derived from it using the method of hypergraph containers.

APA, Harvard, Vancouver, ISO, and other styles

11

MUBAYI, DHRUV, and CAROLINE TERRY. "An Extremal Graph Problem with a Transcendental Solution." Combinatorics, Probability and Computing 28, no. 2 (June 26, 2018): 303–24. http://dx.doi.org/10.1017/s0963548318000299.

Full text

Abstract:

We prove that the number of multigraphs with vertex set {1, . . .,n} such that every four vertices span at most nine edges isan2+o(n2)whereais transcendental (assuming Schanuel's conjecture from number theory). This is an easy consequence of the solution to a related problem about maximizing the product of the edge multiplicities in certain multigraphs, and appears to be the first explicit (somewhat natural) question in extremal graph theory whose solution is transcendental. These results may shed light on a question of Razborov, who asked whether there are conjectures or theorems in extremal combinatorics which cannot be proved by a certain class of finite methods that include Cauchy–Schwarz arguments.Our proof involves a novel application of Zykov symmetrization applied to multigraphs, a rather technical progressive induction, and a straightforward use of hypergraph containers.

APA, Harvard, Vancouver, ISO, and other styles

12

KEEVASH, PETER, and WILLIAM LOCHET. "The Structure of Typical Eye-Free Graphs and a Turán-Type Result for Two Weighted Colours." Combinatorics, Probability and Computing 26, no. 6 (July 31, 2017): 886–910. http://dx.doi.org/10.1017/s0963548317000293.

Full text

Abstract:

The (a,b)-eye is the graph Ia,b = Ka+b \ Kb obtained by deleting the edges of a clique of size b from a clique of size a+b. We show that for any a,b ≥ 2 and p ∈ (0,1), if we condition the random graph G ~ G(n,p) on having no induced copy of Ia,b, then with high probability G is close to an a-partite graph or the complement of a (b−1)-partite graph. Our proof uses the recently developed theory of hypergraph containers, and a stability result for an extremal problem with two weighted colours. We also apply the stability method to obtain an exact Turán-type result for this extremal problem.

APA, Harvard, Vancouver, ISO, and other styles

13

BOLLOBÁS, BÉLA, IMRE LEADER, and CLAUDIA MALVENUTO. "Daisies and Other Turán Problems." Combinatorics, Probability and Computing 20, no. 5 (August 18, 2011): 743–47. http://dx.doi.org/10.1017/s0963548311000319.

Full text

Abstract:

Our aim in this note is to make some conjectures about extremal densities of daisy-free families, where a ‘daisy’ is a certain hypergraph. These questions turn out to be related to some Turán problems in the hypercube, but they are also natural in their own right. We start by giving the daisy conjectures, and some related problems, and shall then go on to describe the connection with vertex-Turán problems in the hypercube.

APA, Harvard, Vancouver, ISO, and other styles

14

Haxell, Penny, Lothar Narins, and Tibor Szabó. "Extremal hypergraphs for Ryser's Conjecture." Journal of Combinatorial Theory, Series A 158 (August 2018): 492–547. http://dx.doi.org/10.1016/j.jcta.2018.04.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Dey, T. K., and J. Pach. "Extremal Problems for Geometric Hypergraphs." Discrete & Computational Geometry 19, no. 4 (April 1998): 473–84. http://dx.doi.org/10.1007/pl00009365.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Łuczak, Tomasz, and Katarzyna Mieczkowska. "On Erdős' extremal problem on matchings in hypergraphs." Journal of Combinatorial Theory, Series A 124 (May 2014): 178–94. http://dx.doi.org/10.1016/j.jcta.2014.01.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Abu-Khazneh, A., János Barát, A. Pokrovskiy, and Tibor Szabó. "A family of extremal hypergraphs for Ryser's conjecture." Journal of Combinatorial Theory, Series A 161 (January 2019): 164–77. http://dx.doi.org/10.1016/j.jcta.2018.07.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Kang, Liying, Lele Liu, Linyuan Lu, and Zhiyu Wang. "The extremal p-spectral radius of Berge hypergraphs." Linear Algebra and its Applications 610 (February 2021): 608–24. http://dx.doi.org/10.1016/j.laa.2020.10.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Gunderson, Karen, and Jason Semeraro. "Tournaments, 4-uniform hypergraphs, and an exact extremal result." Journal of Combinatorial Theory, Series B 126 (September 2017): 114–36. http://dx.doi.org/10.1016/j.jctb.2017.04.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Zhou, Yacong, Liying Kang, Lele Liu, and Erfang Shan. "Extremal problems for the p-spectral radius of Berge hypergraphs." Linear Algebra and its Applications 600 (September 2020): 22–39. http://dx.doi.org/10.1016/j.laa.2020.04.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Gunderson, David S., Vojtěch Rödl, and Alexander Sidorenko. "Extremal Problems for Sets Forming Boolean Algebras and Complete Partite Hypergraphs." Journal of Combinatorial Theory, Series A 88, no. 2 (November 1999): 342–67. http://dx.doi.org/10.1006/jcta.1999.2973.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Dudek, Andrzej, Joanna Polcyn, and Andrzej Ruciński. "Subhypergraph counts in extremal and random hypergraphs and the fractional q-independence." Journal of Combinatorial Optimization 19, no. 2 (July 17, 2008): 184–99. http://dx.doi.org/10.1007/s10878-008-9174-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Razborov, Alexander A. "Flag algebras." Journal of Symbolic Logic 72, no. 4 (December 2007): 1239–82. http://dx.doi.org/10.2178/jsl/1203350785.

Full text

Abstract:

AbstractAsymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with ∣M∣ elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M1,N),…, p(Mh,N), where M1,…, M1, are fixed “template” models and ∣N∣ grows to infinity?In this paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density.

APA, Harvard, Vancouver, ISO, and other styles

24

BRANDT, AXEL, DAVID IRWIN, and TAO JIANG. "Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians." Combinatorics, Probability and Computing 26, no. 3 (March 29, 2017): 367–405. http://dx.doi.org/10.1017/s0963548316000444.

Full text

Abstract:

Given a family ofr-uniform hypergraphs${\cal F}$(orr-graphs for brevity), the Turán number ex(n,${\cal F})$of${\cal F}$is the maximum number of edges in anr-graph onnvertices that does not contain any member of${\cal F}$. A pair {u,v} iscoveredin a hypergraphGif some edge ofGcontains {u, v}. Given anr-graphFand a positive integerp⩾n(F), wheren(F) denotes the number of vertices inF, letHFpdenote ther-graph obtained as follows. Label the vertices ofFasv1,. . .,vn(F). Add new verticesvn(F)+1,. . .,vp. For each pair of verticesvi, vjnot covered inF, add a setBi,jofr− 2 new vertices and the edge {vi, vj} ∪Bi,j, where theBi,jare pairwise disjoint over all such pairs {i, j}. We callHFpthe expanded p-clique with an embedded F. For a relatively large family ofF, we show that for all sufficiently largen, ex(n,HFp) = |Tr(n, p− 1)|, whereTr(n, p− 1) is the balanced complete (p− 1)-partiter-graph onnvertices. We also establish structural stability of near-extremal graphs. Our results generalize or strengthen several earlier results and provide a class of hypergraphs for which the Turán number is exactly determined (for largen).

APA, Harvard, Vancouver, ISO, and other styles

25

Rüttimann, Gottfried T. "The Approximate Jordan-Hahn Decomposition." Canadian Journal of Mathematics 41, no. 6 (December 1, 1989): 1124–46. http://dx.doi.org/10.4153/cjm-1989-050-5.

Full text

Abstract:

Non-commutative measure theory embraces measure theory on cr-fields of subsets of a set, on projection lattices of von Neumann algebras or JBW-algebras and on hypergraphs alike [20], [27], [33], [37], [39], [40], [41]. Due to the unifying structure of an orthoalgebra concepts can easily be transferred from one branch to the other. Additional conceptual inpetus is obtained from the logico-probabilistic foundations of quantum mechanics (see [6], [19], [21]).In the late seventies the author studied the Jordan-Hahn decomposition of measures on orthomodular posets and certain graphs. These investigations revealed an interesting geometrical aspect of this decomposition in that the Jordan-Hahn property of the convex set of probability charges on a finite orthomodular poset can be characterized in terms of the extreme points of the unit ball of the Banach space dual of the base normed space of Jordan charges.

APA, Harvard, Vancouver, ISO, and other styles

26

Hou, Yuan, An Chang, and Joshua Cooper. "Spectral Extremal Results for Hypergraphs." Electronic Journal of Combinatorics 28, no. 3 (August 27, 2021). http://dx.doi.org/10.37236/9018.

Full text

Abstract:

Let $F$ be a graph. A hypergraph is called Berge $F$ if it can be obtained by replacing each edge in $F$ by a hyperedge containing it. Given a family of graphs $\mathcal{F}$, we say that a hypergraph $H$ is Berge $\mathcal{F}$-free if for every $F \in \mathcal{F}$, the hypergraph $H$ does not contain a Berge $F$ as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Turán-type problems over linear $k$-uniform hypergraphs by using spectral methods, including a tight result on Berge $C_4$-free linear $3$-uniform hypergraphs.

APA, Harvard, Vancouver, ISO, and other styles

27

Sundberg, Eric Lars. "Extremal Hypergraphs for the Biased Erdős-Selfridge Theorem." Electronic Journal of Combinatorics 20, no. 1 (February 5, 2013). http://dx.doi.org/10.37236/2394.

Full text

Abstract:

A positional game is essentially a generalization of Tic-Tac-Toe played on a hypergraph $(V,{\cal F}).$ A pivotal result in the study of positional games is the Erdős–Selfridge theorem, which gives a simple criterion for the existence of a Breaker's winning strategy on a finite hypergraph ${\cal F}$. It has been shown that the bound in the Erdős–Selfridge theorem can be tight and that numerous extremal hypergraphs exist that demonstrate the tightness of the bound. We focus on a generalization of the Erdős–Selfridge theorem proven by Beck for biased $(p:q)$ games, which we call the $(p:q)$–Erdős–Selfridge theorem. We show that for $pn$-uniform hypergraphs there is a unique extremal hypergraph for the $(p:q)$–Erdős–Selfridge theorem when $q\geq 2$.

APA, Harvard, Vancouver, ISO, and other styles

28

Mubayi, Dhruv, and John Talbot. "Extremal Problems for $t$-Partite and $t$-Colorable Hypergraphs." Electronic Journal of Combinatorics 15, no. 1 (February 4, 2008). http://dx.doi.org/10.37236/750.

Full text

Abstract:

Fix integers $t \ge r \ge 2$ and an $r$-uniform hypergraph $F$. We prove that the maximum number of edges in a $t$-partite $r$-uniform hypergraph on $n$ vertices that contains no copy of $F$ is $c_{t, F}{n \choose r} +o(n^r)$, where $c_{t, F}$ can be determined by a finite computation. We explicitly define a sequence $F_1, F_2, \ldots$ of $r$-uniform hypergraphs, and prove that the maximum number of edges in a $t$-chromatic $r$-uniform hypergraph on $n$ vertices containing no copy of $F_i$ is $\alpha_{t,r,i}{n \choose r} +o(n^r)$, where $\alpha_{t,r,i}$ can be determined by a finite computation for each $i\ge 1$. In several cases, $\alpha_{t,r,i}$ is irrational. The main tool used in the proofs is the Lagrangian of a hypergraph.

APA, Harvard, Vancouver, ISO, and other styles

29

Cameron, Alex. "Extremal Numbers for Directed Hypergraphs with Two Edges." Electronic Journal of Combinatorics 25, no. 1 (March 16, 2018). http://dx.doi.org/10.37236/6507.

Full text

Abstract:

Let a $2 \rightarrow 1$ directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such directed hypergraph $F$, let the $n$th extremal number of $F$ be the maximum number of edges that any directed hypergraph on $n$ vertices can have without containing a copy of $F$. In 2007, Langlois, Mubayi, Sloan, and Turán determined the exact extremal number for a particular directed hypergraph and found the extremal number up to asymptotic equivalence for a second directed hypergraph. Each of these forbidden graphs had exactly two edges. In this paper, we determine the exact extremal numbers for every $2 \rightarrow 1$ directed hypergraph that has exactly two edges.

APA, Harvard, Vancouver, ISO, and other styles

30

Ergemlidze, Beka, Ervin Győri, and Abhishek Methuku. "The Exact Linear Turán Number of the Sail." Electronic Journal of Combinatorics 28, no. 4 (December 3, 2021). http://dx.doi.org/10.37236/9904.

Full text

Abstract:

A hypergraph is linear if any two of its edges intersect in at most one vertex. The sail (or $3$-fan) $F^3$ is the $3$-uniform linear hypergraph consisting of $3$ edges $f_1, f_2, f_3$ pairwise intersecting in the same vertex $v$ and an additional edge $g$ intersecting each $f_i$ in a vertex different from $v$. The linear Turán number $\mathrm{ex}_{\mathrm{lin}}(n, F^3)$ is the maximum number of edges in a $3$-uniform linear hypergraph on $n$ vertices that does not contain a copy of $F^3$. Füredi and Gyárfás proved that if $n = 3k$, then $\mathrm{ex}_{\mathrm{lin}}(n, F^3) = k^2$ and the only extremal hypergraphs in this case are transversal designs. They also showed that if $n = 3k+2$, then $\mathrm{ex}_{\mathrm{lin}}(n, F^3) = k^2+k$, and the only extremal hypergraphs are truncated designs (which are obtained from a transversal design on $3k+3$ vertices with $3$ groups by removing one vertex and all the hyperedges containing it) along with three other small hypergraphs. However, the case when $n =3k+1$ was left open. In this paper, we solve this remaining case by proving that $\mathrm{ex}_{\mathrm{lin}}(n, F^3) = k^2+1$ if $n = 3k+1$, answering a question of Füredi and Gyárfás. We also characterize all the extremal hypergraphs. The difficulty of this case is due to the fact that these extremal examples are rather non-standard. In particular, they are not derived from transversal designs like in the other cases.

APA, Harvard, Vancouver, ISO, and other styles

31

Kang, Liying, Lele Liu, and Erfang Shan. "Sharp Lower Bounds on the Spectral Radius of Uniform Hypergraphs Concerning Degrees." Electronic Journal of Combinatorics 25, no. 2 (April 13, 2018). http://dx.doi.org/10.37236/6644.

Full text

Abstract:

Let $\mathcal{A}(H)$ and $\mathcal{Q}(H)$ be the adjacency tensor and signless Laplacian tensor of an $r$-uniform hypergraph $H$. Denote by $\rho(H)$ and $\rho(\mathcal{Q}(H))$ the spectral radii of $\mathcal{A}(H)$ and $\mathcal{Q}(H)$, respectively. In this paper we present a lower bound on $\rho(H)$ in terms of vertex degrees and we characterize the extremal hypergraphs attaining the bound, which solves a problem posed by Nikiforov [Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455–535]. Also, we prove a lower bound on $\rho(\mathcal{Q}(H))$ concerning degrees and give a characterization of the extremal hypergraphs attaining the bound.

APA, Harvard, Vancouver, ISO, and other styles

32

Mofidi, Alireza. "ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION." Facta Universitatis, Series: Mathematics and Informatics, April 12, 2022, 121. http://dx.doi.org/10.22190/fumi210301011m.

Full text

Abstract:

The number of the cycles in a graph is an important well-known parameter in graph theory and there are a lot of investigations carried out in the literature for finding suitable bounds for it. In this paper, we delve into studying this parameter and the cycle structure of graphs through the lens of the cycle hypergraphs and VC-dimension and find some new bounds for it, where the cycle hypergraph of a graph is a hypergraph with the edges of the graph as its vertices and the edge sets of the cycles as its hyperedges respectively. Note that VC-dimension is an important notion in extremal combinatorics, graph theory, statistics and machine learning. We investigate cycle hypergraph from the perspective of VC-theory, specially the celebrated Sauer-Shelah lemma, in order to give our upper and lower bounds for the number of the cycles in terms of the (dual) VC-dimension of the cycle hypergraph and nullity of graph. We compute VC-dimension and the mentioned bounds in some graph classes and also show that in certain classes, our bounds are sharper than many previous ones in the literature.

APA, Harvard, Vancouver, ISO, and other styles

33

Chernikov, Artem, and Sergei Starchenko. "Definable Regularity Lemmas for NIP Hypergraphs." Quarterly Journal of Mathematics, March 12, 2021. http://dx.doi.org/10.1093/qmath/haab011.

Full text

Abstract:

Abstract We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and Lov\'asz-Szegedy for graphs of bounded VC-dimension. We also consider the two extremal cases of regularity for stable and distal hypergraphs, improving and generalizing the corresponding results for graphs in the literature. Finally, we consider a related question of the existence of large (approximately) homogeneous definable subsets of NIP hypergraphs and provide some positive results and counterexamples, in particular for graphs definable in the p-adics.

APA, Harvard, Vancouver, ISO, and other styles

34

Cherkashin, Danila. "Coloring Cross-Intersecting Families." Electronic Journal of Combinatorics 25, no. 1 (March 2, 2018). http://dx.doi.org/10.37236/7162.

Full text

Abstract:

Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erdős-Ko-Rado theorem. On the other hand, P. Erdős and L. Lovász in their noted 1975 paper posed problems on coloring intersecting families as a restriction of classical hypergraph coloring problems to a special class of hypergraphs. This note deals with the mentioned coloring problems stated for cross-intersecting families.

APA, Harvard, Vancouver, ISO, and other styles

35

Johnston, J. Travis, and Linyuan Lu. "Turán Problems on Non-Uniform Hypergraphs." Electronic Journal of Combinatorics 21, no. 4 (October 30, 2014). http://dx.doi.org/10.37236/3901.

Full text

Abstract:

A non-uniform hypergraph $H=(V,E)$ consists of a vertex set $V$ and an edge set $E\subseteq 2^V$; the edges in $E$ are not required to all have the same cardinality. The set of all cardinalities of edges in $H$ is denoted by $R(H)$, the set of edge types. For a fixed hypergraph $H$, the Turán density $\pi(H)$ is defined to be $\lim_{n\to\infty}\max_{G_n}h_n(G_n)$, where the maximum is taken over all $H$-free hypergraphs $G_n$ on $n$ vertices satisfying $R(G_n)\subseteq R(H)$, and $h_n(G_n)$, the so called Lubell function, is the expected number of edges in $G_n$ hit by a random full chain. This concept, which generalizes the Turán density of $k$-uniform hypergraphs, is motivated by recent work on extremal poset problems. The details connecting these two areas will be revealed in the end of this paper.Several properties of Turán density, such as supersaturation, blow-up, and suspension, are generalized from uniform hypergraphs to non-uniform hypergraphs. Other questions such as "Which hypergraphs are degenerate?" are more complicated and don't appear to generalize well. In addition, we completely determine the Turán densities of $\{1,2\}$-hypergraphs.

APA, Harvard, Vancouver, ISO, and other styles

36

Pelekis, Christos, and Israel Rocha. "A Generalization of Erdős' Matching Conjecture." Electronic Journal of Combinatorics 25, no. 2 (May 11, 2018). http://dx.doi.org/10.37236/7420.

Full text

Abstract:

Let $\mathcal{H}=(V,\mathcal{E})$ be an $r$-uniform hypergraph on $n$ vertices and fix a positive integer $k$ such that $1\le k\le r$. A $k$-matching of $\mathcal{H}$ is a collection of edges $\mathcal{M}\subset \mathcal{E}$ such that every subset of $V$ whose cardinality equals $k$ is contained in at most one element of $\mathcal{M}$. The $k$-matching number of $\mathcal{H}$ is the maximum cardinality of a $k$-matching. A well-known problem, posed by Erdős, asks for the maximum number of edges in an $r$-uniform hypergraph under constraints on its $1$-matching number. In this article we investigate the more general problem of determining the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices subject to the constraint that its $k$-matching number is strictly less than $a$. The problem can also be seen as a generalization of the well-known $k$-intersection problem. We propose candidate hypergraphs for the solution of this problem, and show that the extremal hypergraph is among this candidate set when $n\ge 4r\binom{r}{k}^2\cdot a$.

APA, Harvard, Vancouver, ISO, and other styles

37

Anstee, R. P., and Ruiyuan Chen. "Forbidden Submatrices: Some New Bounds and Constructions." Electronic Journal of Combinatorics 20, no. 1 (January 14, 2013). http://dx.doi.org/10.37236/2166.

Full text

Abstract:

We explore an extremal hypergraph problem for which both the vertices and edges are ordered. Given a hypergraph $F$ (not necessarily simple), we consider how many edges a simple hypergraph (no repeated edges) on $m$ vertices can have while forbidding $F$ as a subhypergraph where both hypergraphs have fixed vertex and edge orderings. A hypergraph of $n$ edges on $m$ vertices can be encoded as an $m\times n$ (0,1)-matrix. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. Given a (0,1)-matrix $F$, we define ${\hbox{fs}}(m,F)$ as the maximum, over all simple matrices $A$ which do not have $F$ as a submatrix, of the number of columns in $A$. The row and column order matter. It is known that if $F$ is $k\times \ell$ then ${\hbox{fs}}(m,F)$ is $O(m^{2k-1-\epsilon})$ where $\epsilon=(k-1)/(13\log_2 \ell)$. Anstee, Frankl, Füredi and Pach have conjectured that if $F$ is $k$-rowed, then ${\hbox{fs}}(m,F)$ is $O(m^k)$. We show ${\hbox{fs}}(m,F)$ is $O(m^2)$ for $F= \left[{1\,0\,1\,0\,1\atop 0\,1\,0\,1\,0}\cdots\right]$ and for $F= \left[{1\,0\,1\,0\,1\atop 1\,0\,1\,0\,1}\cdots\right]$. The proofs use a type of amortized analysis. We also give some constructions.

APA, Harvard, Vancouver, ISO, and other styles

38

Klazar, Martin. "Counting Pattern-free Set Partitions II: Noncrossing and Other Hypergraphs." Electronic Journal of Combinatorics 7, no. 1 (May 23, 2000). http://dx.doi.org/10.37236/1512.

Full text

Abstract:

A (multi)hypergraph ${\cal H}$ with vertices in ${\bf N}$ contains a permutation $p=a_1a_2\ldots a_k$ of $1, 2, \ldots, k$ if one can reduce ${\cal H}$ by omitting vertices from the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to ${\cal H}_p=(\{i, k+a_i\}:\ i=1, \ldots, k)$. We formulate six conjectures stating that if ${\cal H}$ has $n$ vertices and does not contain $p$ then the size of ${\cal H}$ is $O(n)$ and the number of such ${\cal H}$s is $O(c^n)$. The latter part generalizes the Stanley–Wilf conjecture on permutations. Using generalized Davenport–Schinzel sequences, we prove the conjectures with weaker bounds $O(n\beta(n))$ and $O(\beta(n)^n)$, where $\beta(n)\rightarrow\infty$ very slowly. We prove the conjectures fully if $p$ first increases and then decreases or if $p^{-1}$ decreases and then increases. For the cases $p=12$ (noncrossing structures) and $p=21$ (nonnested structures) we give many precise enumerative and extremal results, both for graphs and hypergraphs.

APA, Harvard, Vancouver, ISO, and other styles

39

Zhang, Yi, Yi Zhao, and Mei Lu. "Vertex Degree Sums for Perfect Matchings in 3-Uniform Hypergraphs." Electronic Journal of Combinatorics 25, no. 3 (September 7, 2018). http://dx.doi.org/10.37236/7658.

Full text

Abstract:

We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without an isolated vertex. Suppose that $H$ is a 3-uniform hypergraph whose order $n$ is sufficiently large and divisible by $3$. If $H$ contains no isolated vertex and $\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different space barrier from the one for the corresponding Dirac problem.

APA, Harvard, Vancouver, ISO, and other styles

40

Füredi, Zoltán, Alexandr Kostochka, and Ruth Luo. "Berge Cycles in Non-Uniform Hypergraphs." Electronic Journal of Combinatorics 27, no. 3 (July 24, 2020). http://dx.doi.org/10.37236/9346.

Full text

Abstract:

We consider two extremal problems for set systems without long Berge cycles. First we give Dirac-type minimum degree conditions that force long Berge cycles. Next we give an upper bound for the number of hyperedges in a hypergraph with bounded circumference. Both results are best possible in infinitely many cases.

APA, Harvard, Vancouver, ISO, and other styles

41

Mubayi, Dhruv, Zoltán Füredi, Jacques Verstraëte, Alexandr Kostochka, and Tao Jiang. "Tight paths in convex geometric hypergraphs." Advances in Combinatorics, February 28, 2020. http://dx.doi.org/10.19086/aic.12044.

Full text

Abstract:

One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $n$-vertex graph with more than $\frac{k-1}{2}n$ edges contains any $k$-edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $r$-uniform hypergraph, i.e., a hypergraph where each edge contains $r$ vertices. A tight tree is an $r$-uniform hypergraph such that there is an ordering $v_1,\ldots,v_n$ of its its vertices with the following property: the vertices $v_1,\ldots,v_r$ form an edge and for every $i>r$, there is a single edge $e$ containing the vertex $v_i$ and $r-1$ of the vertices $v_1,\ldots,v_{i-1}$, and $e\setminus\{v_i\}$ is a subset of one of the edges consisting only of vertices from $v_1,\ldots,v_{i-1}$. The conjecture of Kalai asserts that every $n$-vertex $r$-uniform hypergraph with more than $\frac{k-1}{r}\binom{n}{r-1}$ edges contains every $k$-edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $n$ for every $r$ and $k$. The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $r$-tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous Erdős-Gallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first non-trivial upper bound valid for all $r$ and $k$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.

APA, Harvard, Vancouver, ISO, and other styles

42

Spiegel, Christoph. "A Note on Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems." Electronic Journal of Combinatorics 24, no. 3 (August 25, 2017). http://dx.doi.org/10.37236/6730.

Full text

Abstract:

We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Rúzsa as well as Rué et al.

APA, Harvard, Vancouver, ISO, and other styles

43

Anstee, R. P., and Santiago Salazar. "Forbidden Berge Hypergraphs." Electronic Journal of Combinatorics 24, no. 1 (March 31, 2017). http://dx.doi.org/10.37236/6482.

Full text

Abstract:

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix $F$, we say that a (0,1)-matrix $A$ has $F$ as a Berge hypergraph if there is a submatrix $B$ of $A$ and some row and column permutation of $F$, say $G$, with $G\le B$. Letting $\|A\|$ denote the number of columns in $A$, we define the extremal function $\mathrm{Bh}(m,{ F})=\max\{\|A\|\,:\, A \hbox{ }m\hbox{-rowed simple matrix and no Berge hypergraph }F\}$. We determine the asymptotics of $\mathrm{Bh}(m,F)$ for all $3$- and $4$-rowed $F$ and most $5$-rowed $F$. For certain $F$, this becomes the problem of determining the maximum number of copies of $K_r$ in a $m$-vertex graph that has no $K_{s,t}$ subgraph, a problem studied by Alon and Shikhelman.

APA, Harvard, Vancouver, ISO, and other styles

44

O'Neill, Jason, and Jacques Verstraete. "A Generalization of the Bollobás Set Pairs Inequality." Electronic Journal of Combinatorics 28, no. 3 (July 2, 2021). http://dx.doi.org/10.37236/9627.

Full text

Abstract:

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $n \geqslant k \geqslant t \geqslant 2$, we consider a collection of $k$ families $\mathcal{A}_i: 1 \leq i \leqslant k$ where $\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$ so that $A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \varnothing$ if and only if there are at least $t$ distinct indices $i_1,i_2,\dots,i_k$. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $\beta_{k,t}(n)$ of the families with ground set $[n]$.

APA, Harvard, Vancouver, ISO, and other styles

45

Lu, Linyuan, and László Székely. "Using Lovász Local Lemma in the Space of Random Injections." Electronic Journal of Combinatorics 14, no. 1 (September 7, 2007). http://dx.doi.org/10.37236/981.

Full text

Abstract:

The Lovász Local Lemma is known to have an extension for cases where independence is missing but negative dependencies are under control. We show that this is often the case for random injections, and we provide easy-to-check conditions for the non-trivial task of verifying a negative dependency graph for random injections. As an application, we prove existence results for hypergraph packing and Turán type extremal problems. A more surprising application is that tight asymptotic lower bounds can be obtained for asymptotic enumeration problems using the Lovász Local Lemma.

APA, Harvard, Vancouver, ISO, and other styles

46

Ruciński, Andrzej, Eliza Jackowska, and Joanna Polcyn. "Multicolor Ramsey Numbers and Restricted Turán Numbers for the Loose 3-Uniform Path of Length Three." Electronic Journal of Combinatorics 24, no. 3 (July 14, 2017). http://dx.doi.org/10.37236/7119.

Full text

Abstract:

Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges $\{a,b,c\}, \{c,d,e\},$ and $\{e,f,g\}$. It is known that the $r$-colored Ramsey number for $P$ is $R(P;r)=r+6$ for $r=2,3$, and that $R(P;r)\le 3r$ for all $r\ge3$. The latter result follows by a standard application of the Turán number $\mathrm{ex}_3(n;P)$, which was determined to be $\binom{n-1}2$ in our previous work. We have also shown that the full star is the only extremal 3-graph for $P$. In this paper, we perform a subtle analysis of the Turán numbers for $P$ under some additional restrictions. Most importantly, we determine the largest number of edges in an $n$-vertex $P$-free 3-graph which is not a star. These Turán-type results, in turn, allow us to confirm the formula $R(P;r)=r+6$ for $r\in\{4,5,6,7\}$.

APA, Harvard, Vancouver, ISO, and other styles

47

Bradač, Domagoj, Matija Bucić, and Benny Sudakov. "Turán numbers of sunflowers." Proceedings of the American Mathematical Society, December 15, 2022. http://dx.doi.org/10.1090/proc/16160.

Full text

Abstract:

A collection of distinct sets is called a sunflower if the intersection of any pair of sets equals the common intersection of all the sets. Sunflowers are fundamental objects in extremal set theory with relations and applications to many other areas of mathematics as well as to theoretical computer science. A central problem in the area due to Erdős and Rado from 1960 asks for the minimum number of sets of size r r needed to guarantee the existence of a sunflower of a given size. Despite a lot of recent attention including a polymath project and some amazing breakthroughs, even the asymptotic answer remains unknown. We study a related problem first posed by Duke and Erdős in 1977 which requires that in addition the intersection size of the desired sunflower be fixed. This question is perhaps even more natural from a graph theoretic perspective since it asks for the Turán number of a hypergraph made by the sunflower consisting of k k edges, each of size r r and with common intersection of size t t . For a fixed size of the sunflower k k , the order of magnitude of the answer has been determined by Frankl and Füredi. In the 1980’s, with certain applications in mind, Chung, Erdős and Graham considered what happens if one allows k k , the size of the desired sunflower, to grow with the size of the ground set. In the three uniform case, r = 3 r=3 , the correct dependence on the size of the sunflower has been determined by Duke and Erdős and independently by Frankl and in the four uniform case by Bucić, Draganić, Sudakov and Tran. We resolve this problem for any uniformity, by determining up to a constant factor the n n -vertex Turán number of a sunflower of arbitrary uniformity r r , common intersection size t t and with the size of the sunflower k k allowed to grow with n n .

APA, Harvard, Vancouver, ISO, and other styles

48

Tang, Zhongzheng, Yucong Tang, and Zhuo Diao. "Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number." Journal of Combinatorial Optimization, August 22, 2022. http://dx.doi.org/10.1007/s10878-022-00893-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Tao, Terence. "A Quantitative Ergodic Theory Proof of Szemerédi's Theorem." Electronic Journal of Combinatorics 13, no. 1 (November 6, 2006). http://dx.doi.org/10.37236/1125.

Full text

Abstract:

A famous theorem of Szemerédi asserts that given any density $0 < \delta \leq 1$ and any integer $k \geq 3$, any set of integers with density $\delta$ will contain infinitely many proper arithmetic progressions of length $k$. For general $k$ there are essentially four known proofs of this fact; Szemerédi's original combinatorial proof using the Szemerédi regularity lemma and van der Waerden's theorem, Furstenberg's proof using ergodic theory, Gowers' proof using Fourier analysis and the inverse theory of additive combinatorics, and the more recent proofs of Gowers and Rödl-Skokan using a hypergraph regularity lemma. Of these four, the ergodic theory proof is arguably the shortest, but also the least elementary, requiring passage (via the Furstenberg correspondence principle) to an infinitary measure preserving system, and then decomposing a general ergodic system relative to a tower of compact extensions. Here we present a quantitative, self-contained version of this ergodic theory proof, and which is "elementary" in the sense that it does not require the axiom of choice, the use of infinite sets or measures, or the use of the Fourier transform or inverse theorems from additive combinatorics. It also gives explicit (but extremely poor) quantitative bounds.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!