103,786 research outputs found
Wheighted expanders and the anisotropic Alon-Boppana theorem
No full textWe present the anisotropic version of the classical Alon–Boppana theorem on the asymptotic
spectrum of random walks on infinite families of graphs
Efficient Removal Lemmas for Matrices
No full textThe authors and Fischer recently proved that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing an (ordered) matrix removal lemma, which states the following: If a matrix is far from satisfying some hereditary property, then a large enough constant-size random submatrix of it does not satisfy the property with probability at least 9/10. Here being far from the property means that one needs to modify a constant fraction of the entries of the matrix to make it satisfy the property.
However, in the above general removal lemma, the required size of the random submatrix grows very fast as a function of the distance of the matrix from satisfying the property. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: If an epsilon-fraction of the entries of a binary matrix M can be covered by pairwise-disjoint copies of some (s x t) matrix A, then a delta-fraction of the (s x t)-submatrices of M are equal to A, where delta is polynomial in epsilon.
We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas
Recursive bounds for perfect hashing
No full textLet k≤b be positive integers. A family C of sequences of length t over an alphabet of size b is called k-separated if for any k distinct members of C, there is a coordinate in which they mutually differ. Let N(t,b,k) denote the maximum size of such a family. This function has been studied extensively, mainly in the context of perfect hashing. Here we slightly improve a recent bound of Dyachkov, showing that for all t<k≤b, N(t,b,k)≤tb-(k-1)(t-1). This implies that if k≤b and t is divisible by k-1, then N(t,b,k)≤(k-1)bt/(k-1)-(k-1)2. © 2001 Elsevier Science B.V
The ε-t-Net Problem
No full textWe study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem.
We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets.
We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest
Product structure extension of the Alon--Seymour--Thomas theorem
No full textAlon, Seymour and Thomas [1990] proved that every -vertex graph excluding as a minor has treewidth less than . Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth , where each vertex is blown up by a complete graph of order . Solving an open problem of Illingworth, Scott and Wood [2022], we prove that the treewidth bound can be reduced to while keeping blowups of order . As an extension of the Lipton--Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to , which is best possible. We generalise this result for -minor-free graphs, with blowups of order . This setting includes graphs embeddable on any fixed surface.Title changed, author added, and results for -minor-free graphs added in v2. Referee comments incorporated into v
Letter, [Author unclear] to Paulina T. Merritt
No full textHandwritten letter to Paulina Merritt from an unknown author, October 1, 1876.
Energy Quantisation and Time Parameterisation
No full textWe show that if space is compact, then trajectories
cannot be defined in the framework of the quantum
Hamilton–Jacobi (HJ) equation. The starting point is the
simple observation that when the energy is quantised it is
not possible to make variations with respect to the energy,
and the time parameterisation t − t_0 = ∂S_0/∂E, implied by
Jacobi’s theorem, which leads to the group velocity, is ill
defined. It should be stressed that this follows directly from
the quantum HJ equation without any axiomatic assumption
concerning the standard formulation of quantum mechanics.
This provides a stringent connection between the quantum HJ
equation and the Copenhagen interpretation. Together with
tunnelling and the energy quantisation theorem for confining
potentials, formulated in the framework of quantum HJ equation,
it leads to the main features of the axioms of quantum
mechanics from a unique geometrical principle. Similar to
the case of the classical HJ equation, this fixes its quantum
analog by requiring that there exist point transformations,
rather than canonical ones, leading to the trivial hamiltonian.
This is equivalent to a basic cocycle condition on the states.
Such a cocycle condition can be implemented on compact
spaces, so that continuous energy spectra are allowed only
as a limiting case. Remarkably, a compact space would also
imply that the Dirac and von Neumann formulations of quantum
mechanics essentially coincide.We suggest that there is
a definition of time parameterisation leading to trajectories
in the context of the quantum HJ equation having the probabilistic
interpretation of the Copenhagen School
Alon-Babai-Suzuki's Conjecture Related to Binary Codes in Nonmodular Version
No full text Let and be sets of nonnegative integers. Let be a family of subsets of with for each and for any . Every subset of can be represented by a binary code a such that if and if . Alon et al. made a conjecture in 1991 in modular version. We prove Alon-Babai-Sukuki's Conjecture in nonmodular version. For any and with , .</p
Efek Pemberian Transcutaneus Electrical Nerve Stimulation (TENS) Menurut Metode God Alon Terhadap Nyeri Punggung Mekanik Kronik
No full textLatar belakang : Nyeri punggung bawah (NPB) adalah salah satu sindroma nyeri yang terjadi pada regio punggung bawah dengan penyebab yang sangat bervariasi antara lain: degenerasi, inflamasi, infeksi, metabolisme, neoplasma,
trauma, konginetal, muskuloskletal, viserogenik, vaskuler, dan psikogenik, serta paska operasi. NPB mekanik mengarah pada NPB yang terjadi pada struktur anatomis punggung bawah yang normal yang digunakan secara berlebihan atau
akibat sekunder dari trauma atau deformitas, yang menimbulkan stress atau strain pada otot, tendon dan ligament. Penanganan penurunan nyeri pada punggung bawah mekanik salah satunya adalah TENS metode God Alon, dimana didalamnya terdapat dua treatment yang diberikan yaitu metode God Alon B ke A dan TENS dengan metode Gad Alon C
ke A. Yang dalam manfaatnya memberikan effek terhadap penurunan rasa nyeri pada kondisi kronik.
Tujuan : Penelitian ini bertujuan untuk mengetahui pengaruh Chest Therapy terhadap pengembangan sangkar thorak penderita PPOK.
Metode penelitian : Penelitian ini dilaksanakan melalui pendekatan kuantitatif dengan metode Quasi eksperimental. Populasi penelitian ini adalah penderita penderita NPB mekanik kronik di Panti Wreda Dharama Bakti Surakarta, sampel berjumlah 20 orang diambil melalui metode Purposive Sampling, pengukuran menggunakan skala pengukuran nyeri VAS.
Hasil : Uji normalitas Shapiro-Wilk untuk nilai nyeri dengan hasil p = > 0,05 yang berarti distribusi data normal, maka di uji Analisis data menggunakan Paired
Sampel T test. Dari hasil uji tersebut menunjukkan adanya pengaruh pemberian TENS metode God Alon B-A dan C-A terhadap penurunan rasa nyeri (p=0,000). Pada uji beda pengaruh menunjukkan bahwa TENS Metode God Alon C-A lebih
dapat menurunkan rasa nyeri.
Kesimpulan: Ada pengaruh TENS Metode God Alon C-A dan B-A terhadap penurunan nyeri NPB mekanik kronik
Handwritten biographical information on Paulina T. McClung Merritt
No full textA handwritten biography of Paulina T. McClung Merritt by an unknown author, 1892.
- …
