107,224 research outputs found
Turan H-densities for 3-graphs
No full textGiven an r-graph H on h vertices, and a family F of forbidden subgraphs, we define ex H (n, F) to be the maximum number of induced copies of H in an F-free r-graph on n vertices. Then the Turan H-density of F is the limit pi(H)(F) = (lim)(n ->infinity) ex(H)(n, F)/((n)(h)) This generalises the notions of Turan-density (when H is an r-edge), and inducibility (when F is empty). Although problems of this kind have received some attention, very few results are known. We use Razborov's semi-definite method to investigate Turan H-densities for 3-graphs. In particular, we show that pi(-)(K4)(K-4) = 16/27, with Turans construction being optimal. We prove a result in a similar flavour for K-5 and make a general conjecture on the value of pi(Kt)-(K-t). We also establish that pi(4.2)(empty set) = 3/4, where 4: 2 denotes the 3-graph on 4 vertices with exactly 2 edges. The lower bound in this case comes from a random geometric construction strikingly different from previous known extremal examples in 3-graph theory. We give a number of other results and conjectures for 3-graphs, and in addition consider the inducibility of certain directed graphs. Let (S) over right arrow (k) be the out-star on k vertices; i.e. the star on k vertices with all k 1 edges oriented away from the centre. We show that pi((S) over right arrow3)(empty set) = 2 root 3 - 3, with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and Rodl on the Turan density of the 3-graph C-5. We also determine pi((S) over right arrowk) (empty set) when k = 4, 5, and conjecture its value for general k
On Turan hypergraphs
No full textLet α(H) be the stability number of a hypergraph H = (X, E). T(n, k, α) is the smallest q such that there exists a k-uniform hypergraph H with n vertices, q edges and with α(H) ≤ α. A k-uniform hypergraph H, with n vertices, T(n, k, α) edges and α(H) ≤α is a Turan hypergraph. The value of T(n, 2, α) is given by a theorem of Turan. In this paper new lower bounds to T(n, k, α) are obtained and it is proved that an infinity of affine spaces are Turan hypergraphs. © 1978.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
l-Degree Turan Density
No full textLet H-n be a k-graph on n vertices. For 0 <= l < k and an l-subset T of V (H-n), define the degree deg(T) of T to be the number of (k - l)-subsets S such that S boolean OR T is an edge in H-n. Let the minimum l-degree of H-n be delta(l) (H-n) = min{deg(T) : T subset of V (H-n) and vertical bar T vertical bar = l}. Given a family F of k-graphs, the l-degree Turan number ex(l) (n, F) is the largest delta(l) (H-n) over all F-free k-graphs H-n on n vertices. Hence, ex(0) (n, F) is the Turan number. We define l-degree Turan density to be pi(kappa)(l) (F) = lim sup(n ->infinity) ex(l)(n, F)/kappa(n-l). In this paper, we show that for k > l > 1, the set of pi(kappa)(l) (F) is dense in the interval [0, 1). Hence, there is no "jump" for l-degree Turan density when k > l > 1. We also give a lower bound on pi(kappa)(l) (F) in terms of an ordinary Turan density
Some exact results for generalized Turan problems
No full textFix a k-chromatic graph F. In this paper we consider the question to determine for which graphs H does the Turan graph Tk-1(n) have the maximum number of copies of H among all n-vertex F-free graphs (for n large enough). We say that such a graph H is F-Turan-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph H, there is k large enough such that H is K-k-Turan-good. (ii) The path P-3 is F-Turan-good for F with chi(F) >= 4. (iii) The path P-4 and cycle C-4 are C5-Turan-good. (iv) The cycle C-4 is F-2-Turan-good where F-2 is the graph of two triangles sharing exactly one vertex
Generalized rainbow Turan problems
No full textAlon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Turan problem: for fixed graphs H and F and an integer n, what is the maximum number of copies of H in an n-vertex F-free graph?An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Turan number of F is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of F. The study of rainbow Turan problems was initiated by Keevash, Mubayi, Sudakov and Verstraete [Comb. Probab. Comput. 16 (2007)].Motivated by the above problems, we study the following problem: What is the maximum number of copies of F in a properly edge-colored graph on n vertices without a rainbow copy of F? We establish several results, including when F is a path, cycle or tree
EDGE ORDERED TURAN PROBLEMS
No full textWe introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge ordered graph with the induced edge order. We say that an edge ordered graph G avoids another edge ordered graph H, if no subgraph of G is isomorphic to H. The Turan number ex(<)'(n, H) of a family H of edge ordered graphs is the maximum number of edges in an edge ordered graph on n vertices that avoids all elements of H.We examine this parameter in general and also for several singleton families of edge orders of certain small specific graphs, like star forests, short paths and the cycle of length four.DC
Replication Data for Compliance with IMF conditions and economic growth
No full textEvrensel, A., Turan, T., Yanikkaya, H. (2023). Compliance with IMF conditions and economic growth, under review
Generalized Turan densities in the hypercube
No full textA classical extremal, or Turan-type problem asks to determine ex(G, H), the largest number of edges in a subgraph of a graph G which does not contain a subgraph isomorphic to H. Alon and Shikhelman introduced the so-called generalized extremal number ex(G, T, H), defined to be the maximum number of subgraphs isomorphic to T in a subgraph of G that contains no subgraphs isomorphic to H. In this paper we investigate the case when G = Qn, the hypercube of dimension n, and T and H are smaller hypercubes or cycles. (c) 2022 Elsevier B.V. All rights reserved
Data for Electronic and structural properties of Rh- and Pd-based kagome-layered shandites from first principles
No full textTwo folders are included: Abinit and Structures. The Structures directory contains the relaxed shandite structures of all the 20 materials simulated in the paper, in the format of .cif files. These files are human readable but can also be opened with the VESTA software or other similar software for visualization. The Abinit directory contains all the input files needed for replicating the calculations whose results are presented in the paper. Abinit 9.10.1 was used, which can be downloaded from [1]. All the calculations used PBEsol of the type PAW JTH v1.1, stringent accuracy and xml format obtained from PseudoDojo [2]. For simplicity, all the Abinit files are given only for the case of Rh3Bi2S2, but one can simply change the names of the atoms and change the structural parameters to run calculations for any of the other 19 compounds.
[1] https://www.abinit.org/
[2] https://www.pseudo-dojo.org/First-principles study of shandites M3A2Ch2, with M=Pd,Rh, A=Bi,In,Pb,Sn,Tl and Ch=S,Se. The density functional theory (DFT) and density functional perturbation theory (DFPT) were carried out using Abinit and the dataset contains all the input files needed to reproduce the results. The dataset contains also the cif files containing the relaxed shandite structure of each compound.Work at the University of Minnesota (L.B. and T.B.) were supported by the NSF CAREER grant DMR-2046020.M.H.C. is supported by ERC grant project 101164202 -- SuperSOC. Funded by the European Union.Buiarelli, Luca; Birol, Turan; Andersen, Brian M; Christensen, Morten H. (2025). Data for Electronic and structural properties of Rh- and Pd-based kagome-layered shandites from first principles. Retrieved from the Data Repository for the University of Minnesota (DRUM), https://doi.org/10.13020/eb0t-x263
Some Exact Ramsey-Turan Numbers
No full textLet r be an integer, f(n) be a function, and H be a graph. Introduced by Erdos, Hajnal, Sos, and Szemeredi, the r-Ramsey-Turan number of H, RTr(n, H, f(n)), is defined to be the maximum number of edges in an n-vertex, H-free graph G with alpha(r)(G) <= f(n), where alpha(r)(G) denotes the K-r-independence number of G.
In this note, using isoperimetric properties of the high-dimensional unit sphere, we construct graphs providing lower bounds for RTr(n, Kr+s, o(n)) for every 2 <= s <= r. These constructions are sharp for an infinite family of pairs of r and s. The only previous sharp construction (for such values of r and s) was by Bollobas and Erdos for r=s=2
- …
